Алгоритм Кнута — Морріса — Пратта (скорочено алгоритм КМП) — один із алгоритмів пошуку рядка, що шукає входження слова W
у рядку S
, використовуючи просте спостереження, що коли відбувається невідповідність, то слово містить у собі достатньо інформації для того, щоб визначити, де наступне входження може початися, таким чином пропускаючи кількаразову перевірку попередньо порівняних символів.
Алгоритм, що винайшли Дональд Кнут та , а також незалежно від них , опубліковано у спільній статті у 1977 році.
Часова асимптотична складність алгоритму становить O(N+M), де N — довжина слова W, M — довжина рядка S.
Теорія
Алгоритм повинен знайти початковий індекс m
рядка W[]
в рядку S[]
.
Найпростіший алгоритм пробігає по всьому рядку S[m]
, де m
— індекс. Якщо індекс m
досягне кінця рядка, то W[]
не знайдено і алгоритм поверне результат «fail». На кожній позиції перевіряється рівність елемента на позиції m
з S[]
й елемента на першій позиції з W[]
, тобто S[m] =? W[0]
. Якщо вони рівні, то алгоритм перевіряє наступні відповідні елементи в рядках за індексом i
. Алгоритм перевіряє всі вирази S[m+i] =? W[i]
. Якщо всі елементи з W
знайдені, то алгоритм поверне позицію m
.
Зазвичай, пробна перевірка швидко відкидає можливість збігу. Якщо рядки складаються з рівномірно розподілених елементів, то шанс, що перші елементи дорівнюють один одному, буде 1 до 26. Отже, в більшості випадків пробна перевірка відкидатиме початкові елементи. Шанс, що перші два елементи будуть рівними, дорівнює 1 до 262 (тобто, 1 до 676). Тобто, якщо елементи рівномірно розподілені, очікувана складність пошуку в рядку S[]
довжини k буде порядку k порівнянь або O(k). Якщо S[]
має 1.000.000.000 елементів і W[]
має 1000 елементів, то пошук рядка займе приблизно 1.000.000.000 порівнянь.
Проте очікувана продуктивність не гарантована. Якщо рядки не випадкові, то на кожному кроці m
може знадобитися багато порівнянь. У найгіршому випадку два рядки збігаються майже за всіма літерами. Якщо рядок S[]
має 1.000.000.000 елементів, що рівні A і рядок W[]
складається з 999 елементів A і останній елемент B. Тоді найпростіший алгоритм на кожному кроці виконуватиме 1000 перевірок, а всіх перевірок буде 1 трильйон. Отже, якщо довжина W[]
— n, то в найгіршому випадку складність становитиме O(k⋅n).
Алгоритм КМП має кращий показник швидкодії в найгіршому випадку. КМП витрачає небагато часу (за порядком розміру W[]
, O(n)) на попереднє обчислення таблиці, і потім використовує таблицю для швидкого пошуку рядка за час O(k).
З іншого боку, на відміну від попередньо розглянутого простого алгоритму, алгоритм КМП використовує відомості про попередні порівняння. У прикладі, що наведений вище, коли КМП зустрічає незбіг на 1000-ному елементі (i
= 999), тобто S[m+999] ≠ W[999]
, КМП знатиме, що 999 позицій вже перевірено. КМП містить ці знання у попередньо обчисленій таблиці і додаткових змінних. Коли КМП знаходить незбіг, з таблиці визначається, наскільки збільшиться змінна m
.
Алгоритм КМП
Приклад алгоритму пошуку
Для пояснення подробиць алгоритму опрацюємо (порівняно штучний) перебіг алгоритму. У будь-який момент, алгоритм перебуває в стані визначеному двома цілими:
m
— позиція вS
, початок сподіваного збігу дляW
,i
— індекс поточного символу уW
.
На кожному кроці алгоритм порівнює S[m+i]
з W[i]
і збільшує i
якщо вони однакові. Це можна побачити на початку наступного пошуку
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Ми рухаємось порівнюючи наступні символи W
із відповідними символами з S
, просуваючись від поточного до наступного в випадку збігу. Однак, на четвертому кроці, ми отримуємо S[3]
як пробіл, а W[3] = 'D'
, розбіжність. Радше ніж починати знов з S[1]
, ми зауважимо, що 'A'
не зустрічається між позиціями 0 і 3 в S
окрім як в 0; відповідно, перевіривши всі ці символи до цього, ми занотували, що неможливо знайти початок збігу, якщо ми пробіжимо їх знов. Отже ми пересуваємось на наступний символ, встановлюючи m = 4
і i = 0
. (m напочатку приймає значення 3 бо m + i - T[i] = 0 + 3 - 0 = 3
і тоді стає 4 бо T[0] = -1
, де T
— це таблиця «часткових збігів»)
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Ми швидко отримуємо майже повний збіг "ABCDAB"
, аж як у W[6]
(S[10]
), знов маємо невідповідність. Однак, лиш саме перед завершенням поточного часткового збігу, ми проминули "AB"
, що може бути початком нового збігу, отже маємо взяти це до уваги. Раз ми вже знаємо, що ці два символи те, що нам потрібно, ми не маємо перевіряти їх знов; ми просто встановлюємо m = 8
, i = 2
і продовжуємо перевіряти поточний символ. Таким чином, ми не тільки опустили символи з S
, що попередньо збіглись, але й символи з W
.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Цей пошук зазнає невдачі одразу, бо наш зразок не містить пробілу, як і за першої спроби, ми повертаємось до початку W
і починаємо пошук на наступному символі S
: m = 11
, встановивши i = 0
.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
І знов ми відразу ж наштовхуємось на відповідність "ABCDAB"
, але наступний символ, 'C'
, не збігається з кінцевим символом 'D'
слова W
. Як і раніше, ми встановлюємо m = 15
, щоб почати з двосимвольного рядку "AB"
, що веде до поточної позиції, встановлюємо i = 2
, і продовжуємо зіставляння з поточної позиції.
1 2 m: 01234567890123456789012 S: ABC ABCDAB ABCDABCDABDE W: ABCDABD i: 0123456
Цього разу ми можемо завершити зіставляння, першим символом якого є S[15]
.
Опис і псевдокод для алгоритму пошуку
Наведений вище приклад показує всі елементи алгоритму. Наразі, припустимо наявність таблиці «часткових збігів» T
, описаної нижче, яка показує де ми маємо почати нове зіставлення в разі невдачі поточного. Записи T
утворені так, що якщо маємо збіг від S[m]
, що зазнав невдачі при порівнянні S[m + i]
з W[i]
, тоді наступний можливий збіг почнеться з індексу m + i - T[i]
в S
(T[i]
це кількість повернень, які ми маємо зробити після невдачі). Це має два наслідки: перший, T[0] = -1
, показує, що якщо W[0]
це не збіг, ми не можемо повернутись і повинні просто перевірити наступний символ; і другий, хоча наступний можливий збіг почнеться з індексу m + i - T[i]
, як у прикладі вище, ми не маємо насправді перевіряти будь-який з символів T[i]
після цього, так що ми продовжуємо пошук з W[T[i]]
. Далі наводиться приклад псевдокоду алгоритму пошуку КМП.
алгоритм пошук_кмп: вхід: масив символів, S (текст пошуку) масив символів, W (шукане слово) вихід: ціле число (базована на нулі позиція в S, в якій знайдено W) визначаємо змінні: ціле число, m ← 0 (початок поточного збігу в S) ціле число, i ← 0 (позиція поточного символу в W) масив цілих чисел, T (таблиця обчислена деінде) доки m+i менша за довжину S, виконувати: якщо W[i] = S[m + i], якщо i дорівнює (довжина W)-1, повернути m нехай i ← i + 1 інакше, нехай m ← m + i - T[i], якщо T[i] більша ніж -1, нехай i ← T[i] інакше нехай i ← 0 (якщо ми потрапили сюди, пошук в S завершився невдачею) повернути довжина S
Швидкодія алгоритму пошуку
Припускаючи існування таблиці T
, пошукова складова алгоритму КМП має складність O(k), де k
це довжина S
. За винятком сталих витрат на виклик функції всі обчислення виконуються циклом while
, ми вирахуємо граничну кількість ітерацій циклу; для цього ми спочатку зробимо спостереження про природу T
. За визначенням вона побудована так, що якщо частковий збіг, що почався в S[m]
, провалився під час порівняння S[m + i]
з W[i]
, тоді наступний можливий збіг має початись в S[m + (i - T[i])]
. Наступний можливий збіг може трапитись лише на більшому індексі ніж m
, з цього випливає, щоT[i] < i
.
Знаючи цей факт, покажемо, що цикл може виконатись не більше 2k
разів. Для кожної ітерації, виконується одна з двох гілок тіла циклу. У першій гілці безумовно збільшується i
і не змінюється m
, так що m + i
індекс символу S
, що ми розглядаємо збільшується. Друга гілка додає i - T[i]
до m
, і як ми бачили це завжди додатне число. Отже, збільшується початок поточного збігу m
. Тепер, цикл завершується якщо m + i = k
; з того що кожна гілка циклу може бути відвідана не більш ніж k
разів, бо вони збільшують відповідно або m + i
або m
, і m ≤ m + i
: якщо m = k
, тоді напевно m + i ≥ k
, з того що воно збільшується щонайбільше на одиницю кожного разу, ми мали мати m + i = k
в якийсь момент у минулому, яким би способом ми не просувались.
Так як цикл виконується не більше ніж 2k
разів, ми показали, що складність алгоритму пошуку O(k)
.
Ось інший спосіб розгляду часу виконання: Скажімо ми починаємо зіставляти W і S в позиціях i та p, якщо W існує як підрядок S в p, тоді W[0 до m] == S[p до p+m]. За умови успіху (W[i] == S[p+i]), ми збільшуємо i на 1 (i++). При невдачі (W[i] != S[p+i]), вказівник у тексті не змінюється, а вказівник в шуканому слові відкочується на певну кількість символів (i = T[i], де T це таблиця переходів). І ми намагаємося зіставити W[T[i]]
з S[p+i]. Найбільший відкіт обмежений i, тобто, для будь-якого незбігу, ми можемо відкотитись щонайбільше на наш поступ до невдачі. Звідси й випливає час 2k.
Таблиця «часткових збігів» (також відома як «функція невдачі»)
Ціль цієї функції дозволити алгоритму уникнути перевірки кожного символу S
більш ніж один раз. Головним спостереженням про природу лінійного пошуку, що дозволяє цьому бути це те, що в перевіреному відтинку головного рядку щодо початкового відтинка зразка, ми точно знаємо в яких місцях новий потенційний збіг, що міг би продовжитись до поточної позиції, міг би починатись перед поточною позицією. Інакше кажучи, ми робимо «перед-пошук» зразка і збираємо список усіх можливих позицій відступу, відтинки від яких до поточної позиції утворюють часткові збіги. T[i]
це довжина найдовшого можливого вірного початкового сегменту W
, який також є відтинком підрядка, що завершується в W[i - 1]
. Ми використовуємо домовленість, що порожній рядок має довжину 0. Через те, що незбіг на самому початку алгоритму — це особливий випадок (не існує можливості відступу), ми встановлюємо T[0] = -1
, як показано вище.
Приклад роботи алгоритму побудови таблиці
Спочатку ми розглянемо приклад W = "ABCDABD"
. Ми побачимо, що він подібний до головного пошуку й ефективний з тих самих причин. Встановлюємо T[0] = -1
. Для знаходження T[1]
, ми маємо виявити суфікс "A"
, який також є префіксом для W
. Але такого суфіксу не існує, отже T[1] = 0
. Так само, T[2] = 0
.
Продовжуючи з T[3]
, ми зауважуємо наявність короткого шляху перевірки всіх суфіксів: припустимо ми знайшли суфікс, що є префіксом і завершується в W[2]
з довжиною 2 (найбільша можлива); тоді його перший символ є префіксом префіксу W
, тобто префіксом сам по собі, і завершується в W[1]
, а ми в випадку T[2] вже визначили, що це неможливо. Отже на кожному кроці, треба перевіряти суфікси довжини m+1 лише якщо було знайдено суфікс довжини m на попередньому кроці(тобто T[x]=m).
Звідси ми навіть не повинні розглядати підрядки довжини 2, і як і на попередньому кроці єдина спроба з довжиною 1 зазнає невдачі, тому T[3] = 0
.
Ми переходимо до наступного W[4]
, 'A'
. Та сама логіка показує, що найдовший підрядок на який треба зважати має довжину 1, і хоча тут 'A'
спрацьовує, згадуємо, що ми шукаємо на сегмент, що завершується до поточного символу; звідси T[4] = 0
також.
Просуваємось до W[5]
, який є 'B'
, ми застосовуємо наступну логіку: якщо ми перед цим знайшли підзразок, що починається перед попереднім символом W[4]
, що триває до поточного W[5]
, тоді зокрема він мав би мати вірний початковий відтинок, що завершується в W[4]
, що заперечується фактом, що ми вже виявили 'A'
як єдиний вірний відтинок, що завершується в W[4]
. З цього випливає, що ми не маємо дивитись до W[4]
. Отже T[5] = 1
.
Нарешті, ми розглядаємо наступний символ у відтинку з початком у W[4] = 'A'
, це буде 'B'
, він збігається з W[5]
. Далі більше, ті ж доводи, що й раніше кажуть, що ми не повинні дивитись перед W[4]
для знаходження відтинку для W[6]
, і ми встановлюємо T[6] = 2
.
Отже ми укладаємо таку таблицю:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 |
---|---|---|---|---|---|---|---|
W[i] | A | B | C | D | A | B | D |
T[i] | −1 | 0 | 0 | 0 | 0 | 1 | 2 |
Інший приклад, цікавіший і складніший:
i | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 0 | 1 | 2 | 3 |
---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
W[i] | P | A | R | T | I | C | I | P | A | T | E | I | N | P | A | R | A | C | H | U | T | E | ||
T[i] | −1 | 0 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 0 | 0 | 0 | 0 | 0 | 0 | 1 | 2 | 3 | 0 | 0 | 0 | 0 | 0 |
Опис і псевдокод алгоритму побудови таблиці
Приклад вище, показує загальну техніку утворення таблиці з найменшими витратами. Загальний принцип пошуку: більша частина роботи виконується до поточного кроку, отже дуже мало треба робити для переходу на наступний. Маленьким ускладненням є те, що логіка вірна в усьому рядку дає невірний результат на початку. Це вимагає деякого початкового коду.
алгоритм таблиця_кмп: вхід: масив символів, W (слово до розбору) масив цілих, T (таблиця до наповнення) вихід: нічого (але під час дії наповнюється таблиця) визначення змінних: ціле, pos ← 2 (поточна позиція в T) ціле, cnd ← 0 (базований на нулі індекс у W наступного
символу в поточному підрядку кандидаті) (перші кілька значень фіксовані, і відрізняються від запропонованих алгоритмом) нехай T[0] ← -1, T[1] ← 0 доки pos менше ніж довжина W, виконувати: (перший варіант: підрядок продовжується) якщо W[pos - 1] = W[cnd],
нехай cnd ← cnd + 1, T[pos] ← cnd, pos ← pos + 1 (другий випадок: не продовжується, але ми можемо відступити) інакше, якщо cnd > 0, нехай cnd ← T[cnd] (третій випадок: ми вичерпали всіх кандидатів. Зауважимо cnd = 0) інакше, нехай T[pos] ← 0, pos ← pos + 1
Швидкодія алгоритму побудови таблиці
Складність табличного алгоритму дорівнює O(n)
, де n
— це довжина W
. За винятком початкового налаштування вся робота виконується в циклі while
, отже достатньо показати, що цей цикл виконується за час O(n)
, чого ми досягнемо через схожі вивчення значень pos
і pos - cnd
. В першій гілці, pos - cnd
зберігається, бо pos
і cnd
збільшуються одночасно, але звісно, pos
збільшилась. В другій гілці, cnd
заміняється на T[cnd]
, як ми бачили вище завжди суворо менша ніж cnd
, отже збільшується pos - cnd
. В третій гілці, pos
збільшується, а cnd
ні, отже pos
і pos - cnd
збільшуються. З того, що pos ≥ pos - cnd
, отримуємо, що на кожному кроці збільшується або pos
або нижня межа для pos
; отже з того, що алгоритм завершується за умови pos = n
, він має завершитись не пізніше 2n
ітерацій циклу, бо pos - cnd
починається з 1
. Значить складність табличного алгоритму становить O(n)
.
Швидкодія алгоритму КМП
Через те, що дві складові алгоритму мають складності, відповідно, O(k)
і O(n)
, складність всього алгоритму становить O(n + k)
.
Складності залишаються незмінними, попри те скільки зразків, що повторюються в W
або S
.
Втілення алгоритму
s = 0; for (i = 1; i <= m; i++) { while (s > 0 && a[i] != b[s+1]) s = f(s); // f - функція невдачі (failure function) if (a[i] == b[s+l]) s = s + 1; if (s == n) return "yes"; } return "no";
Посилання
- An explanation of the algorithm [ 16 січня 2021 у Wayback Machine.]
- Knuth-Morris-Pratt algorithm [ 25 січня 2021 у Wayback Machine.]
Література
- Donald Knuth; James H. Morris, Jr, Vaughan Pratt (1977). . SIAM Journal on Computing. 6 (2): 323—350. Архів оригіналу за 4 січня 2010. Процитовано 15 жовтня 2006.
Вікіпедія, Українська, Україна, книга, книги, бібліотека, стаття, читати, завантажити, безкоштовно, безкоштовно завантажити, mp3, відео, mp4, 3gp, jpg, jpeg, gif, png, малюнок, музика, пісня, фільм, книга, гра, ігри, мобільний, телефон, android, ios, apple, мобільний телефон, samsung, iphone, xiomi, xiaomi, redmi, honor, oppo, nokia, sonya, mi, ПК, web, Інтернет
Algoritm Knuta Morrisa Pratta skorocheno algoritm KMP odin iz algoritmiv poshuku ryadka sho shukaye vhodzhennya slova W u ryadku S vikoristovuyuchi proste sposterezhennya sho koli vidbuvayetsya nevidpovidnist to slovo mistit u sobi dostatno informaciyi dlya togo shob viznachiti de nastupne vhodzhennya mozhe pochatisya takim chinom propuskayuchi kilkarazovu perevirku poperedno porivnyanih simvoliv Algoritm sho vinajshli Donald Knut ta a takozh nezalezhno vid nih opublikovano u spilnij statti u 1977 roci Chasova asimptotichna skladnist algoritmu stanovit O N M de N dovzhina slova W M dovzhina ryadka S TeoriyaAlgoritm povinen znajti pochatkovij indeks m ryadka W v ryadku S Najprostishij algoritm probigaye po vsomu ryadku S m de m indeks Yaksho indeks m dosyagne kincya ryadka to W ne znajdeno i algoritm poverne rezultat fail Na kozhnij poziciyi pereviryayetsya rivnist elementa na poziciyi m z S j elementa na pershij poziciyi z W tobto S m W 0 Yaksho voni rivni to algoritm pereviryaye nastupni vidpovidni elementi v ryadkah za indeksom i Algoritm pereviryaye vsi virazi S m i W i Yaksho vsi elementi z W znajdeni to algoritm poverne poziciyu m Zazvichaj probna perevirka shvidko vidkidaye mozhlivist zbigu Yaksho ryadki skladayutsya z rivnomirno rozpodilenih elementiv to shans sho pershi elementi dorivnyuyut odin odnomu bude 1 do 26 Otzhe v bilshosti vipadkiv probna perevirka vidkidatime pochatkovi elementi Shans sho pershi dva elementi budut rivnimi dorivnyuye 1 do 262 tobto 1 do 676 Tobto yaksho elementi rivnomirno rozpodileni ochikuvana skladnist poshuku v ryadku S dovzhini k bude poryadku k porivnyan abo O k Yaksho S maye 1 000 000 000 elementiv i W maye 1000 elementiv to poshuk ryadka zajme priblizno 1 000 000 000 porivnyan Prote ochikuvana produktivnist ne garantovana Yaksho ryadki ne vipadkovi to na kozhnomu kroci m mozhe znadobitisya bagato porivnyan U najgirshomu vipadku dva ryadki zbigayutsya majzhe za vsima literami Yaksho ryadok S maye 1 000 000 000 elementiv sho rivni A i ryadok W skladayetsya z 999 elementiv A i ostannij element B Todi najprostishij algoritm na kozhnomu kroci vikonuvatime 1000 perevirok a vsih perevirok bude 1 triljon Otzhe yaksho dovzhina W n to v najgirshomu vipadku skladnist stanovitime O k n Algoritm KMP maye krashij pokaznik shvidkodiyi v najgirshomu vipadku KMP vitrachaye nebagato chasu za poryadkom rozmiru W O n na poperednye obchislennya tablici i potim vikoristovuye tablicyu dlya shvidkogo poshuku ryadka za chas O k Z inshogo boku na vidminu vid poperedno rozglyanutogo prostogo algoritmu algoritm KMP vikoristovuye vidomosti pro poperedni porivnyannya U prikladi sho navedenij vishe koli KMP zustrichaye nezbig na 1000 nomu elementi i 999 tobto S m 999 W 999 KMP znatime sho 999 pozicij vzhe perevireno KMP mistit ci znannya u poperedno obchislenij tablici i dodatkovih zminnih Koli KMP znahodit nezbig z tablici viznachayetsya naskilki zbilshitsya zminna m Algoritm KMPPriklad algoritmu poshuku Dlya poyasnennya podrobic algoritmu opracyuyemo porivnyano shtuchnij perebig algoritmu U bud yakij moment algoritm perebuvaye v stani viznachenomu dvoma cilimi m poziciya v S pochatok spodivanogo zbigu dlya W i indeks potochnogo simvolu u W Na kozhnomu kroci algoritm porivnyuye S m i z W i i zbilshuye i yaksho voni odnakovi Ce mozhna pobachiti na pochatku nastupnogo poshuku 1 2 m 01234567890123456789012 S ABC ABCDAB ABCDABCDABDE W ABCD ABD i 0123456 Mi ruhayemos porivnyuyuchi nastupni simvoli W iz vidpovidnimi simvolami z S prosuvayuchis vid potochnogo do nastupnogo v vipadku zbigu Odnak na chetvertomu kroci mi otrimuyemo S 3 yak probil a W 3 D rozbizhnist Radshe nizh pochinati znov z S 1 mi zauvazhimo sho A ne zustrichayetsya mizh poziciyami 0 i 3 v S okrim yak v 0 vidpovidno perevirivshi vsi ci simvoli do cogo mi zanotuvali sho nemozhlivo znajti pochatok zbigu yaksho mi probizhimo yih znov Otzhe mi peresuvayemos na nastupnij simvol vstanovlyuyuchi m 4 i i 0 m napochatku prijmaye znachennya 3 bo m i T i 0 3 0 3 i todi staye 4 bo T 0 1 de T ce tablicya chastkovih zbigiv 1 2 m 01234567890123456789012 S ABC ABCDAB ABCDABCDABDE W ABCDABD i 0123456 Mi shvidko otrimuyemo majzhe povnij zbig ABCDAB azh yak u W 6 S 10 znov mayemo nevidpovidnist Odnak lish same pered zavershennyam potochnogo chastkovogo zbigu mi prominuli AB sho mozhe buti pochatkom novogo zbigu otzhe mayemo vzyati ce do uvagi Raz mi vzhe znayemo sho ci dva simvoli te sho nam potribno mi ne mayemo pereviryati yih znov mi prosto vstanovlyuyemo m 8 i 2 i prodovzhuyemo pereviryati potochnij simvol Takim chinom mi ne tilki opustili simvoli z S sho poperedno zbiglis ale j simvoli z W 1 2 m 01234567890123456789012 S ABC ABCDAB ABCDABCDABDE W ABC DABD i 0123456 Cej poshuk zaznaye nevdachi odrazu bo nash zrazok ne mistit probilu yak i za pershoyi sprobi mi povertayemos do pochatku W i pochinayemo poshuk na nastupnomu simvoli S m 11 vstanovivshi i 0 1 2 m 01234567890123456789012 S ABC ABCDAB ABCDABCDABDE W ABCDABD i 0123456 I znov mi vidrazu zh nashtovhuyemos na vidpovidnist ABCDAB ale nastupnij simvol C ne zbigayetsya z kincevim simvolom D slova W Yak i ranishe mi vstanovlyuyemo m 15 shob pochati z dvosimvolnogo ryadku AB sho vede do potochnoyi poziciyi vstanovlyuyemo i 2 i prodovzhuyemo zistavlyannya z potochnoyi poziciyi 1 2 m 01234567890123456789012 S ABC ABCDAB ABCDABCDABD E W ABCDABD i 0123456 Cogo razu mi mozhemo zavershiti zistavlyannya pershim simvolom yakogo ye S 15 Opis i psevdokod dlya algoritmu poshuku Navedenij vishe priklad pokazuye vsi elementi algoritmu Narazi pripustimo nayavnist tablici chastkovih zbigiv T opisanoyi nizhche yaka pokazuye de mi mayemo pochati nove zistavlennya v razi nevdachi potochnogo Zapisi T utvoreni tak sho yaksho mayemo zbig vid S m sho zaznav nevdachi pri porivnyanni S m i z W i todi nastupnij mozhlivij zbig pochnetsya z indeksu m i T i v S T i ce kilkist povernen yaki mi mayemo zrobiti pislya nevdachi Ce maye dva naslidki pershij T 0 1 pokazuye sho yaksho W 0 ce ne zbig mi ne mozhemo povernutis i povinni prosto pereviriti nastupnij simvol i drugij hocha nastupnij mozhlivij zbig pochnetsya z indeksu m i T i yak u prikladi vishe mi ne mayemo naspravdi pereviryati bud yakij z simvoliv T i pislya cogo tak sho mi prodovzhuyemo poshuk z W T i Dali navoditsya priklad psevdokodu algoritmu poshuku KMP algoritm poshuk kmp vhid masiv simvoliv S tekst poshuku masiv simvoliv W shukane slovo vihid cile chislo bazovana na nuli poziciya v S v yakij znajdeno W viznachayemo zminni cile chislo m 0 pochatok potochnogo zbigu v S cile chislo i 0 poziciya potochnogo simvolu v W masiv cilih chisel T tablicya obchislena deinde doki m i mensha za dovzhinu S vikonuvati yaksho W i S m i yaksho i dorivnyuye dovzhina W 1 povernuti m nehaj i i 1 inakshe nehaj m m i T i yaksho T i bilsha nizh 1 nehaj i T i inakshe nehaj i 0 yaksho mi potrapili syudi poshuk v S zavershivsya nevdacheyu povernuti dovzhina S Shvidkodiya algoritmu poshuku Pripuskayuchi isnuvannya tablici T poshukova skladova algoritmu KMP maye skladnist O k de k ce dovzhina S Za vinyatkom stalih vitrat na viklik funkciyi vsi obchislennya vikonuyutsya ciklom b while b mi virahuyemo granichnu kilkist iteracij ciklu dlya cogo mi spochatku zrobimo sposterezhennya pro prirodu T Za viznachennyam vona pobudovana tak sho yaksho chastkovij zbig sho pochavsya v S m provalivsya pid chas porivnyannya S m i z W i todi nastupnij mozhlivij zbig maye pochatis v S m i T i Nastupnij mozhlivij zbig mozhe trapitis lishe na bilshomu indeksi nizh m z cogo viplivaye shoT i lt i Znayuchi cej fakt pokazhemo sho cikl mozhe vikonatis ne bilshe 2k raziv Dlya kozhnoyi iteraciyi vikonuyetsya odna z dvoh gilok tila ciklu U pershij gilci bezumovno zbilshuyetsya i i ne zminyuyetsya m tak sho m i indeks simvolu S sho mi rozglyadayemo zbilshuyetsya Druga gilka dodaye i T i do m i yak mi bachili ce zavzhdi dodatne chislo Otzhe zbilshuyetsya pochatok potochnogo zbigu m Teper cikl zavershuyetsya yaksho m i k z togo sho kozhna gilka ciklu mozhe buti vidvidana ne bilsh nizh k raziv bo voni zbilshuyut vidpovidno abo m i abo m i m m i yaksho m k todi napevno m i k z togo sho vono zbilshuyetsya shonajbilshe na odinicyu kozhnogo razu mi mali mati m i k v yakijs moment u minulomu yakim bi sposobom mi ne prosuvalis Tak yak cikl vikonuyetsya ne bilshe nizh 2k raziv mi pokazali sho skladnist algoritmu poshuku O k Os inshij sposib rozglyadu chasu vikonannya Skazhimo mi pochinayemo zistavlyati W i S v poziciyah i ta p yaksho W isnuye yak pidryadok S v p todi W 0 do m S p do p m Za umovi uspihu W i S p i mi zbilshuyemo i na 1 i Pri nevdachi W i S p i vkazivnik u teksti ne zminyuyetsya a vkazivnik v shukanomu slovi vidkochuyetsya na pevnu kilkist simvoliv i T i de T ce tablicya perehodiv I mi namagayemosya zistaviti W T i z S p i Najbilshij vidkit obmezhenij i tobto dlya bud yakogo nezbigu mi mozhemo vidkotitis shonajbilshe na nash postup do nevdachi Zvidsi j viplivaye chas 2k Tablicya chastkovih zbigiv takozh vidoma yak funkciya nevdachi Cil ciyeyi funkciyi dozvoliti algoritmu uniknuti perevirki kozhnogo simvolu S bilsh nizh odin raz Golovnim sposterezhennyam pro prirodu linijnogo poshuku sho dozvolyaye comu buti ce te sho v perevirenomu vidtinku golovnogo ryadku shodo pochatkovogo vidtinka zrazka mi tochno znayemo v yakih miscyah novij potencijnij zbig sho mig bi prodovzhitis do potochnoyi poziciyi mig bi pochinatis pered potochnoyu poziciyeyu Inakshe kazhuchi mi robimo pered poshuk zrazka i zbirayemo spisok usih mozhlivih pozicij vidstupu vidtinki vid yakih do potochnoyi poziciyi utvoryuyut chastkovi zbigi T i ce dovzhina najdovshogo mozhlivogo virnogo pochatkovogo segmentu W yakij takozh ye vidtinkom pidryadka sho zavershuyetsya v W i 1 Mi vikoristovuyemo domovlenist sho porozhnij ryadok maye dovzhinu 0 Cherez te sho nezbig na samomu pochatku algoritmu ce osoblivij vipadok ne isnuye mozhlivosti vidstupu mi vstanovlyuyemo T 0 1 yak pokazano vishe Priklad roboti algoritmu pobudovi tablici Spochatku mi rozglyanemo priklad W ABCDABD Mi pobachimo sho vin podibnij do golovnogo poshuku j efektivnij z tih samih prichin Vstanovlyuyemo T 0 1 Dlya znahodzhennya T 1 mi mayemo viyaviti sufiks A yakij takozh ye prefiksom dlya W Ale takogo sufiksu ne isnuye otzhe T 1 0 Tak samo T 2 0 Prodovzhuyuchi z T 3 mi zauvazhuyemo nayavnist korotkogo shlyahu perevirki vsih sufiksiv pripustimo mi znajshli sufiks sho ye prefiksom i zavershuyetsya v W 2 z dovzhinoyu 2 najbilsha mozhliva todi jogo pershij simvol ye prefiksom prefiksu W tobto prefiksom sam po sobi i zavershuyetsya v W 1 a mi v vipadku T 2 vzhe viznachili sho ce nemozhlivo Otzhe na kozhnomu kroci treba pereviryati sufiksi dovzhini m 1 lishe yaksho bulo znajdeno sufiks dovzhini m na poperednomu kroci tobto T x m Zvidsi mi navit ne povinni rozglyadati pidryadki dovzhini 2 i yak i na poperednomu kroci yedina sproba z dovzhinoyu 1 zaznaye nevdachi tomu T 3 0 Mi perehodimo do nastupnogo W 4 A Ta sama logika pokazuye sho najdovshij pidryadok na yakij treba zvazhati maye dovzhinu 1 i hocha tut A spracovuye zgaduyemo sho mi shukayemo na segment sho zavershuyetsya do potochnogo simvolu zvidsi T 4 0 takozh Prosuvayemos do W 5 yakij ye B mi zastosovuyemo nastupnu logiku yaksho mi pered cim znajshli pidzrazok sho pochinayetsya pered poperednim simvolom W 4 sho trivaye do potochnogo W 5 todi zokrema vin mav bi mati virnij pochatkovij vidtinok sho zavershuyetsya v W 4 sho zaperechuyetsya faktom sho mi vzhe viyavili A yak yedinij virnij vidtinok sho zavershuyetsya v W 4 Z cogo viplivaye sho mi ne mayemo divitis do W 4 Otzhe T 5 1 Nareshti mi rozglyadayemo nastupnij simvol u vidtinku z pochatkom u W 4 A ce bude B vin zbigayetsya z W 5 Dali bilshe ti zh dovodi sho j ranishe kazhut sho mi ne povinni divitis pered W 4 dlya znahodzhennya vidtinku dlya W 6 i mi vstanovlyuyemo T 6 2 Otzhe mi ukladayemo taku tablicyu i 0 1 2 3 4 5 6W i A B C D A B DT i 1 0 0 0 0 1 2 Inshij priklad cikavishij i skladnishij i 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3W i P A R T I C I P A T E I N P A R A C H U T ET i 1 0 0 0 0 0 0 0 1 2 0 0 0 0 0 0 1 2 3 0 0 0 0 0Opis i psevdokod algoritmu pobudovi tablici Priklad vishe pokazuye zagalnu tehniku utvorennya tablici z najmenshimi vitratami Zagalnij princip poshuku bilsha chastina roboti vikonuyetsya do potochnogo kroku otzhe duzhe malo treba robiti dlya perehodu na nastupnij Malenkim uskladnennyam ye te sho logika virna v usomu ryadku daye nevirnij rezultat na pochatku Ce vimagaye deyakogo pochatkovogo kodu algoritm tablicya kmp vhid masiv simvoliv W slovo do rozboru masiv cilih T tablicya do napovnennya vihid nichogo ale pid chas diyi napovnyuyetsya tablicya viznachennya zminnih cile pos 2 potochna poziciya v T cile cnd 0 bazovanij na nuli indeks u W nastupnogo simvolu v potochnomu pidryadku kandidati pershi kilka znachen fiksovani i vidriznyayutsya vid zaproponovanih algoritmom nehaj T 0 1 T 1 0 doki pos menshe nizh dovzhina W vikonuvati pershij variant pidryadok prodovzhuyetsya yaksho W pos 1 W cnd nehaj cnd cnd 1 T pos cnd pos pos 1 drugij vipadok ne prodovzhuyetsya ale mi mozhemo vidstupiti inakshe yaksho cnd gt 0 nehaj cnd T cnd tretij vipadok mi vicherpali vsih kandidativ Zauvazhimo cnd 0 inakshe nehaj T pos 0 pos pos 1 Shvidkodiya algoritmu pobudovi tablici Skladnist tablichnogo algoritmu dorivnyuye O n de n ce dovzhina W Za vinyatkom pochatkovogo nalashtuvannya vsya robota vikonuyetsya v cikli b while b otzhe dostatno pokazati sho cej cikl vikonuyetsya za chas O n chogo mi dosyagnemo cherez shozhi vivchennya znachen pos i pos cnd V pershij gilci pos cnd zberigayetsya bo pos i cnd zbilshuyutsya odnochasno ale zvisno pos zbilshilas V drugij gilci cnd zaminyayetsya na T cnd yak mi bachili vishe zavzhdi suvoro mensha nizh cnd otzhe zbilshuyetsya pos cnd V tretij gilci pos zbilshuyetsya a cnd ni otzhe pos i pos cnd zbilshuyutsya Z togo sho pos pos cnd otrimuyemo sho na kozhnomu kroci zbilshuyetsya abo pos abo nizhnya mezha dlya pos otzhe z togo sho algoritm zavershuyetsya za umovi pos n vin maye zavershitis ne piznishe 2n iteracij ciklu bo pos cnd pochinayetsya z 1 Znachit skladnist tablichnogo algoritmu stanovit O n Shvidkodiya algoritmu KMPCherez te sho dvi skladovi algoritmu mayut skladnosti vidpovidno O k i O n skladnist vsogo algoritmu stanovit O n k Skladnosti zalishayutsya nezminnimi popri te skilki zrazkiv sho povtoryuyutsya v W abo S Vtilennya algoritmus 0 for i 1 i lt m i while s gt 0 amp amp a i b s 1 s f s f funkciya nevdachi failure function if a i b s l s s 1 if s n return yes return no PosilannyaAn explanation of the algorithm 16 sichnya 2021 u Wayback Machine Knuth Morris Pratt algorithm 25 sichnya 2021 u Wayback Machine LiteraturaDonald Knuth James H Morris Jr Vaughan Pratt 1977 SIAM Journal on Computing 6 2 323 350 Arhiv originalu za 4 sichnya 2010 Procitovano 15 zhovtnya 2006