Найдовший спільний підрядок

Найдовший спільний підрядок (Шаблон: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).