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

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.