Найдовший спільний підрядок (англ. longest common substring) — підрядок двох або більше рядків, що має максимальну довжину.
Формально, найдовшим спільним підрядком рядків
називається рядок
, що задовольняє умові
, операція
позначає що рядок
є (можливо невласним) підрядком рядка
.
Розв'язання задачі пошуку найдовшого спільного підрядка для двох рядків
і
, довжини яких
і
відповідно, полягає в заповненні таблиці
розміром
за наступним правилом, приймаючи, що символи в рядку нумеруються від одиниці.
Максимальне число
в таблиці це і є довжина найбільшого спільного підрядка, сам підрядок:
и
.
У таблиці заповнені значення для рядків 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).