Наибольшая общая подстрока (англ. longest common substring) — подстрока двух или более строк, имеющая максимальную длину.
Формально, наибольшей общей подстрокой строк s 1 , s 2 , … s n {\displaystyle s_{1},s_{2},\ldots s_{n}} называется строка w ∗ {\displaystyle \left.w^{*}\right.} , которая удовлетворяет условию ‖ w ∗ ‖ = max ( { ‖ w ‖ | w ⊑ s i , i = 1 , … n } ) {\displaystyle \|w^{*}\|=\max(\{\|w\||w\sqsubseteq s_{i},i=1,\ldots n\})} , операция w ⊑ s i {\displaystyle w\sqsubseteq s_{i}} обозначает что строка w {\displaystyle \left.w\right.} является (возможно несобственной) подстрокой строки s i {\displaystyle \left.s_{i}\right.} .
Решение задачи поиска наибольшей общей подстроки для двух строк s 1 {\displaystyle \left.s_{1}\right.} и s 2 {\displaystyle \left.s_{2}\right.} , длины которых m {\displaystyle \left.m\right.} и n {\displaystyle \left.n\right.} соответственно, заключается в заполнении таблицы A i j {\displaystyle \left.A_{ij}\right.} размером ( m + 1 ) × ( n + 1 ) {\displaystyle (m+1)\times (n+1)} по следующему правилу, принимая, что символы в строке нумеруются от единицы.
{ A 0 j = 0 , j = 0 … n , A i 0 = 0 , i = 0 … m , A i j = 0 , s 1 [ i ] ≠ s 2 [ j ] , i ≠ 0 , j ≠ 0 , A i j = A i − 1 j − 1 + 1 , s 1 [ i ] = s 2 [ j ] , i ≠ 0 , j ≠ 0. {\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.}
Максимальное число A u v {\displaystyle \left.A_{uv}\right.} в таблице это и есть длина наибольшей общей подстроки, сама подстрока:
s 1 [ u − A u v + 1 ] … s 1 [ u ] {\displaystyle s_{1}[u-A_{uv}+1]\ldots s_{1}[u]} и s 2 [ v − A u v + 1 ] … s 2 [ v ] {\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).