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

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

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

Розв'язання задачі пошуку найдовшого спільного підрядка для двох рядків ${\displaystyle \left.s_{1}\right.}$ і ${\displaystyle \left.s_{2}\right.}$, довжини яких ${\displaystyle \left.m\right.}$ і ${\displaystyle \left.n\right.}$ відповідно, полягає в заповненні таблиці ${\displaystyle \left.A_{ij}\right.}$ розміром ${\displaystyle (m+1)\times (n+1)}$ за наступним правилом, приймаючи, що символи в рядку нумеруються від одиниці.

${\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]\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.}$

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

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