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

Наибольшая общая подстрока (Шаблон:Lang-en) — подстрока двух или более строк, имеющая максимальную длину.

Формально, наибольшей общей подстрокой строк $s_1,s_2,\dots s_n$ называется строка $w^{*}$, которая удовлетворяет условию $\Vert w^{*}\Vert =\max (\{\Vert w\Vert |w⊑s_i,i=1,\dots n\})$, операция $w⊑s_i$ обозначает что строка $w$ является (возможно несобственной) подстрокой строки $s_i$.

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

$\{\begin{array}{cccc}{A}_{0j}& =& 0,& j=0\dots n,\\ A_{i0}& =& 0,& i=0\dots 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}$

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

$s_1[u-A_{uv}+1]\dots s_1[u]$ и $s_2[v-A_{uv}+1]\dots 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).

См. также

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