Наибольшая общая подстрока

Материал из Википедии — свободной энциклопедии
Перейти к: навигация, поиск

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

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

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

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

и .

В таблице заполнены значения для строк 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).

См. также[править | править код]

Примечания[править | править код]