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

Наибольшая общая подстрока (англ. 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).

См. также

Примечания

    This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.