Наибольшая общая подстрока () — подстрока двух или более строк, имеющая максимальную длину.

Формально, наибольшей общей подстрокой строк называется строка , которая удовлетворяет условию , операция обозначает что строка является (возможно несобственной) подстрокой строки .

Решение задачи поиска наибольшей общей подстроки для двух строк и , длины которых и соответственно, заключается в заполнении таблицы размером по следующему правилу, принимая, что символы в строке нумеруются от единицы.

Максимальное число в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

и .

В таблице заполнены значения для строк SUBSEQUENCE и SUBEUENCS:

SUBSEQUENCE 000000000000 S 010010000000 U 002000010000 B 000300000000 E 000001001001 U 001000010000 E 000001002001 N 000000000300 C 000000000040 S 010010000000

Получаем наибольшую общую подстроку UENC.

Сложность такого алгоритма составляет O(mn).

См. также Суффиксное дерево Алгоритмы на строках Наибольшая общая подпоследовательность

Примечания

Категория:Строковые алгоритмы