Найдовший спільний підрядок (англ. 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).
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Najdovshij spilnij pidryadok angl longest common substring pidryadok dvoh abo bilshe ryadkiv sho maye maksimalnu dovzhinu Formalno najdovshim spilnim pidryadkom ryadkiv s 1 s 2 s n displaystyle s 1 s 2 ldots s n nazivayetsya ryadok w displaystyle left w right sho zadovolnyaye umovi w max w w s i i 1 n displaystyle w max w w sqsubseteq s i i 1 ldots n operaciya w s i displaystyle w sqsubseteq s i poznachaye sho ryadok w displaystyle left w right ye mozhlivo nevlasnim pidryadkom ryadka s i displaystyle left s i right Rozv yazannya zadachi poshuku najdovshogo spilnogo pidryadka dlya dvoh ryadkiv s 1 displaystyle left s 1 right i s 2 displaystyle left s 2 right dovzhini yakih m displaystyle left m right i n displaystyle left n right vidpovidno polyagaye v zapovnenni tablici A i j displaystyle left A ij right rozmirom m 1 n 1 displaystyle m 1 times n 1 za nastupnim pravilom prijmayuchi sho simvoli v ryadku numeruyutsya vid odinici 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 amp amp 0 amp j 0 ldots n A i0 amp amp 0 amp i 0 ldots m A ij amp amp 0 amp s 1 i neq s 2 j i neq 0 j neq 0 A ij amp amp A i 1j 1 1 amp s 1 i s 2 j i neq 0 j neq 0 end array right Maksimalne chislo A u v displaystyle left A uv right v tablici ce i ye dovzhina najbilshogo spilnogo pidryadka sam pidryadok s 1 u A u v 1 s 1 u displaystyle s 1 u A uv 1 ldots s 1 u i s 2 v A u v 1 s 2 v displaystyle s 2 v A uv 1 ldots s 2 v U tablici zapovneni znachennya dlya ryadkiv SUBSEQUENCE i SUBEUENCS SUBSEQUENCE 000000000000 S 010010000000 U 002000010000 B 000300000000 E 000001001001 U 001000010000 E 000001002001 N 000000000300 C 000000000040 S 010010000000 Otrimuyemo najdovshij spilnij pidryadok UENC Skladnist takogo algoritmu stanovit O mn