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

Наибольшая общая подстрока (англ. longest common substring) — подстрока двух или более строк, имеющая максимальную длину. Формально, наибольшей общей подстрокой строк называется строка , которая удовлетворяет условию , операция обозначает что строка является (возможно несобственной) подстрокой строки . Решение задачи поиска наибольшей общей подстроки для двух строк и , длины которых и соответственно, заключается в заполнении таблицы размером по следующему правилу, принимая, что символы в строке нумеруются от единицы. Максимальное число в таблице это и есть длина наибольшей общей подстроки, сама подстрока: и . В таблице заполнены значения для строк SUBSEQUENCE и SUBEUENCS: SUBSEQUENCE 000000000000S 010010000000U 002000010000B 000300000000E 000001001001U 001000010000E 000001002001N 000000000300C 000000000040S 010010000000 Получаем наибольшую общую подстроку UENC. Сложность такого алгоритма составляет O(mn).