Це маленьке диво — алгоритм Кнута-Морріса-Пратта (КМП)

Алгоритм Кнута-Моррса-Пратта використовується для пошуку підрядка (зразка) в рядку. Здається, що може бути простіше: рухаємося по рядку і порівнюємо послідовно символи з зразком. Не співпало, переміщаємо початок порівняння на один крок і знову порівнюємо. І так до тих пір, поки не знайдемо зразок або не досягнемо кінця рядка.

Функція приблизно така:
// простий пошук зразка в рядку
// повертає індекс початку зразка в рядку або -1, якщо не знайдений
int find(char *зразок, char *рядок) 
{
// i-з якого місця рядка шукаємо
// j-з якого місця зразка шукаємо
for (int i=0;рядок[i]; i++) {
for (int j=0;; j++) {
if (!зразок[j]) return i; // зразок знайдено 
if(рядок[i+j]!=зразок[j]) break;
}
// поки не знайдений, продовжимо зовнішній цикл
}
// зразка немає
return -1;
}

Простий випадок пошуку
'голка' — зразок
'стогистогстогигстогстогиглстогстогголкастігголкастіг' — рядок пошуку

Складний випадок пошуку
aabbaab
aabaabbaaabaabaabaabaabbaabb

Функція працює і досить спритно, якщо зразки і рядок «хороші». Хороші — це коли внутрішній цикл переривається швидко (1-3 кроці, скажімо, як у простому випадку). Але якщо зразок і рядок містять часто повторювані вкладені шматки (як складному випадку вище), то внутрішній цикл обривається ближче до кінця зразка і час пошуку оцінюється як Про(<довжина зразка>*<довжина рядка>). Якщо довжина рядка 100тис, а довжина зразка 100, то отримуємо О(10 млн). Звичайно, реально рідко зустрінеш зразок довжиною 100, але в олімпіадних завданнях «пошук» це звична справа, тому там простий пошук часто не підходить.

А якщо рядок — це довгий текст, а зразок-фрагмент слова, і треба знайти усі входження цього фрагмента, причому на льоту, по мірі набору слова (помічали, як швидко це роблять браузери)? Алгоритм КМП знаходить всі входження зразка в рядок і його швидкість(<довжина зразка>+<довжина рядка>), тому на великих текстах/зразках або на слабких процесорах (як в низькобюджетних стільникових) він поза конкуренцією.

А тепер подивимося на заголовок? Чому «маленьке»? Тому, що родзинка КМП — це префікс-функція, а вона дійсно маленька. А чому «диво»? Тому що, він начебто вирішує зовсім іншу задачу і це рішення, після деякого чудесного трюку, перетворюється в рішення задачі пошуку всіх входжень зразка в рядок.

Для того, щоб зрозуміти, що і як робить префіксна функція, подивимося на складну рядок
a a b a a b a a a a b a a b а a a b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
0 1 0 1 2 3 4 5 2 2 3 4 5 6 7 8 9 3
Рядок над нею — номер (позиція) символу в рядку (для зручності опису алгоритму вважаємо номер с 1), а найбільша нижня рядок — масив M довжин префіксів, ключ до розуміння префікс-функції.
Візьмемо символ з номером 7 (це a) і для K від 1 до 6 розглянемо рядки-префікси (рядок, що починається з першого індексу рядка) і суфікси (підрядок, останній символ якої у рядку в позиції 7 ( це «наш» символ a) довжини K.

K текст суфікс
1 а a тут все просто: префікс — це перший символ рядка, а суфікс-наш символ a
2 aa ba
3 aab aba
4 aaba aaba найдовше збіг, причому тут і нижче суфікс та префікс почали перекриватися (як фрагменти рядка пошуку)
5 aabaa baaba
6 aabaab abaaba
Зверніть увагу: для довжини 4 суфікс (як послідовність символів) збігається з префіксом і це максимальне значення K при якому суфікс збігається з префіксом. Саме воно і заноситься у відповідну позицію (7) масиву довжин префіксів.
Можна помітити, що для K=7 префікс теж співпаде з суфіксом, оскільки це одна і та ж рядок. Але цей тривіальний випадок нам не підходить, тому що для роботи алгоритму потрібні саме підрядка.

Позначимо S-вихідна рядок, S(n) -початок (префікс) рядка S довжини n, S[n]-символ в позиції n рядка S. M[n] значення в масиві, S(M[n])- та сама рядок, яка є префіксом і суфіксом максимальної довжини для позиції n (для стислості позначимо її P(n)). Рядок P(n) як би «віртуальна», вона не формується і нікуди не пишеться. Це просто початковий фрагмент1 вихідної рядка S довжини M[n]. І цей початковий фрагмент1 співпадає (як послідовність символів) з фрагментом2 довжини M[n], останній символ якого в позиції n. Якщо M[n]=0, то совпаденией немає.

Маємо: позиція 7 масиву заповнена значенням М[7]=4, найдовша рядок P(7)='aaba' довжини 4 (природно), треба перейти до позиції 8 і заповнити M[8]. Можна тупо порахувати всі префікси і суфікси довжиною від 1 до 7, порівняти їх і записати максимальну довжину в позицію 8. Але ми підемо іншим шляхом (слідом за КМП). Нехай знайдена максимально довга рядок P(8) довжини k, яка префікс і суфікс позиції 8. Рядок p7 з перших k-1 символів є префіксом і суфіксом для позиції k-1. Не факт, що для 7й позиції вона найдовша. Однак, якщо виявилося, що p7=P7, P8 — це розширення P7 на один символ. Щоб перевірити, чи можна розширити P7 на одну позицію, треба перевірити, чи збігається додається до суфікс символ-це символ S[8]=a) з наступним символом префікса. Наступний символ префікса a знаходиться в позиції М[7]+1=5 (поміркуйте, чому так). Якщо збігся (а в нашому випадку він збігся), то завдання виконане — М[8]=М[7]+1, а P(8)=P(7)+символ у 8 позиції S[8]=a. Отримуємо P(8)='aabaa'. При успішному розширенні треба всього одне порівняння для обчислення чергового значення масиву. До речі, звідси випливає, що при русі вздовж масиву значення можуть зростати максимум на 1.
Для зручності повторю складну рядок, щоб не потрібно було переміщатися вгору-вниз.
a a b a a b a a a a b a a b а a a b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18
0 1 0 1 2 3 4 5 2 2 3 4 5 6 7 8 9 3
Тепер інший випадок — P8 розширити не вдалося, тобто символ S[9]=a не збігся з символом рядка S у позиції M[8]+1=5 b. Суфікс розширюється легко (оскільки новий символ просто дописується в кінець), а з префіксом проблеми, т. к. додається до суфікс символ може не збігтися з черговим символом префікса. Якщо префікс P(k) не підходить, треба знайти інший такий префікс, коротше, у якого такий же суфікс і спробувати розширити його. Але префікс коротше, причому з таким же суфіксом — це S[M[M[k]]), оскільки при заповненні масиву М кожен елемент містить довжину максимально довгого префікса з таким же суфіксом. Тому, якщо не вдалося розширити S(M[k]) пробуємо так само розширити S(M[M[k]]) і т. д, поки не співпаде або поки не отримаємо нульову довжину (тоді черговий символ S треба просто порівняти з 1м символом рядка S). Цикл перебору походять префіксів закінчується дуже швидко, тому що вся необхідна для цього інформація вже сидить у масиві М.

Для нашої рядка P(8) — це просто розширення P(7) на один символ, знадобилося 1 порівняння. Проте P(8) не вдалося розширити до P(9), оскільки S[9]=a, а S[M[8]+1=6] =b. Раз не підійшов префікс P8 довжини M[8]=5, пробуємо префікс довжини M[5]=2. Він теж не підходить: S[2+1] =b. Пробуємо префікс довжини M[2]=1 і його можна розширити, т. к. S[1+1] =a. Тому M[9]=2, на одиницю більше довжини розширюваного префікса. Для заповнення M[10] треба 2 порівняння (можете перевірити). А от щоб заповнити елементи з 11 по 17, знадобиться по одному порівнянні. В результаті розрахунок значень масиву займає час приблизно О(довжина рядка).
Отже, з алгоритмом заповнення більш-менш ясно.

Переходимо до трюку.
Для знаходження зразка ааbаа в рядку ааbааbааааbааbаааb склеим зразок з рядком ось так ааbаа@ааbааbааааbааbаааb викличемо для неї префікс-функції для заповнення масиву.
a a b a a @ a a b a a b a a a a b a a b а a a b
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
0 1 0 1 2 0 1 2 3 4 5 3 4 5 2 2 3 4 5 3 4 5 2 3
Символ '@' грає роль роздільника, його свідомо немає ні в зразку, ні в рядку пошуку (потрібно підібрати саме такий символ). Подивимося на позиції 11, 14, 19, 22 масиву. Значення в масиві дорівнюють 5, це означає, що суфікс довжиною 5 (фрагмент рядка пошуку) збігається з 5 символами префікса. А 5 символів префікса — це і є зразок для пошуку! Алгоритм пошуку вийдуть такий — склеюємо з допомогою роздільника зразок і рядок пошуку, передаємо «склейку» префиксной функції і потім шукаємо в масиві елементи, рівні довжині зразка, Можна помітити, що значення більше довжини зразка не буде через символ-роздільник, а значення, рівні довжині зразка можуть з'явитися тільки в позиціях, відповідних вихідної рядку пошуку. Склеєна рядок має довжину <довжина зразка>+<довжина рядка>, тому час розрахунку оцінюється як Про(<довжина зразка>+<довжина рядка>), як і говорилося на початку статті.

Префікс-функція
А тепер приклади префікс-функції. Відміну від опису вище в тому, що, як прийнято в Сі-мовах, індекси рахуються з 0.

Приклад на C++

Функція повертає вектор довжин префіксів рядків, а рядок передається як string (не треба обчислювати довжину)
vector<int> prefix_function (string s) {
int n = (int) s.length();
vector<int> pi (n); // в i-му елементі (його індекс i-1) кількість збіглися символів на початку і кінці построки довжини i. 
// p[0]=0 завжди, p[1]=1, якщо починається з двох однакових 
for (int i=1; i < n; ++i) 
{
int j = pi[i-1];
while ((j > 0) && (s[i] != s[j])) // не рівні
j = pi[j-1]; // беремо раніше розраховане значення (починаючи з максимально можливих)
if (s[i] == s[j]) // рівні 
++j; 
pi[i] = j;
}
return p;
} 


Приклад на C

Функція нічого не повертає. Перший параметр — покажчик на рядок, другий — вказівник на заповнюється масив довжин префіксів, третій р — довжина рядка та масиву.
void prefix_function (char *s, int *p, int n) {
pi[0]=0; // в i-му елементі (його індекс i-1) кількість збіглися символів на початку і кінці построки довжини i. 
// p[0]=0 завжди, p[1]=1, якщо починається з двох однакових 
for (int i=1; i < n; ++i) 
{
int j = pi[i-1];
while ((j > 0) && (s[i] != s[j])) // не рівні
j = pi[j-1]; // беремо раніше розраховане значення (починаючи з максимально можливих)
if (s[i] == s[j]) // рівні 
++j; 
pi[i] = j;
}
} 


Моя розповідь про маленькому диво — алгоритм КМП підійшов до кінця. Звичайно, ця стаття про КМП далеко-далеко не перша і, напевно, не остання. Ось дві статті тут, на хабрахабр: Пошук підрядка. Алгоритм Кнута–Морріса-Пратта і Пошук підрядка і суміжні питання.
Але я сподіваюся, хтось вважатиме цю статтю корисною для себе, а хтось (адже може таке трапитися) стане застосовувати КМП. Навіть якщо він не цілком розібрався з внутрішнім механізмом його роботи (розібратися ніколи не пізно).

Алгоритм КМП не єдиний швидкий алгоритм пошуку, але він досить швидкий (для задач типу олімпіадних) і при цьому простий. У деяких випадках алгоритмАгв — Корасик може виявитися ефективніше. Але ті, кому дійсно потрібен цей алгоритм, не потребують популярному викладі, імхо.

Для тих, хто дочитав статтю до кінця, наведу ілюстрації, що показують, як організовані префиксно-суффиксные блоки в досить складних випадках:
ІлюстраціїРядок нулів і одиниць однакові, тільки в перших двох ілюстраціях індекси з 0, а в наступних — з 1. Насправді, це не принципово, оскільки в масив пишуться довжини підрядків, а спосіб нумерації символів в рядку ролі не грає.
Остання ілюстрація — погляд з висоти пташиного польоту» на префікси-суфікси рядків
habrhabhabrhabrhabrhabhabrhabhabrhabhabrhabrhabrhabhabrhabra
без індексів масивів і довжин.




Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.