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

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

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

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

[math]\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] \ne s_2[j],i\ne 0, j\ne 0,\\ A_{ij}&=&A_{i-1j-1}+1,&s_1[i] = s_2[j],i\ne 0,j\ne 0. \end{array} \right. }[/math]

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

[math]\displaystyle{ s_1[u-A_{uv}+1]\ldots s_1[u] }[/math] и [math]\displaystyle{ s_2[v-A_{uv}+1]\ldots s_2[v] }[/math].

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

См. также

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