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

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

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

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

$\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.$

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

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

См. такжеПравить

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