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

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

Формально, наибольшей общей подстрокой строк ${\displaystyle s_{1},s_{2},\ldots s_{n}}$ называется строка ${\displaystyle \left.w^{*}\right.}$, которая удовлетворяет условию ${\displaystyle \|w^{*}\|=\max(\{\|w\||w\sqsubseteq s_{i},i=1,\ldots n\})}$, операция ${\displaystyle w\sqsubseteq s_{i}}$ обозначает что строка ${\displaystyle \left.w\right.}$ является (возможно несобственной) подстрокой строки ${\displaystyle \left.s_{i}\right.}$.

Решение задачи поиска наибольшей общей подстроки для двух строк ${\displaystyle \left.s_{1}\right.}$ и ${\displaystyle \left.s_{2}\right.}$, длины которых ${\displaystyle \left.m\right.}$ и ${\displaystyle \left.n\right.}$ соответственно, заключается в заполнении таблицы ${\displaystyle \left.A_{ij}\right.}$ размером ${\displaystyle (m+1)\times (n+1)}$ по следующему правилу, принимая, что символы в строке нумеруются от единицы.

${\displaystyle \left\{{\begin{array}{rclr}A_{0j}&=&0,&j=0\ldots n,\\A_{i0}&=&0,&i=0\ldots m,\\A_{ij}&=&0,&s_{1}[i]\neq s_{2}[j],i\neq 0,j\neq 0,\\A_{ij}&=&A_{i-1j-1}+1,&s_{1}[i]=s_{2}[j],i\neq 0,j\neq 0.\end{array}}\right.}$

Максимальное число ${\displaystyle \left.A_{uv}\right.}$ в таблице это и есть длина наибольшей общей подстроки, сама подстрока:

${\displaystyle s_{1}[u-A_{uv}+1]\ldots s_{1}[u]}$ и ${\displaystyle s_{2}[v-A_{uv}+1]\ldots s_{2}[v]}$.

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

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

В статье не хватает ссылок на источники (см. рекомендации по поиску). Информация должна быть проверяема, иначе она может быть удалена. Вы можете отредактировать статью, добавив ссылки на авторитетные источники в виде сносок. (7 июня 2019)