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

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

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

Розв'язання задачі пошуку найдовшого спільного підрядка для двох рядків $\left.s_{1}\right.$ і $\left.s_{2}\right.$, довжини яких $\left.m\right.$ і $\left.n\right.$ відповідно, полягає в заповненні таблиці $\left.A_{ij}\right.$ розміром $(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.$

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

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