Алгоритм Кнута-Морріса-Пратта

Це завдання є класичним прикладом застосування префікс-функції (і, власне, вона була відкрита саме у зв'язку з цим).

Дано текст $t$ та рядок $s$. Потрібно знайти та вивести всі позиції входження рядка $s$ у текст $t$.

Алгоритм

Позначимо для зручності через $n$ довжину рядка $s$, а через $m$ — довжину тексту $t$.

Утворимо рядок $s + \# + t$, де символ $\#$ — це роздільник, який не повинен зустрічатися ніде більше. Обчислимо для цього рядка префікс-функцію. Тепер розглянемо її значення, окрім перших $n+1$ (які, як видно, належать до рядка $s$ і роздільника). За визначенням, значення $\pi[i]$ показує найдовшу довжину підрядка, що закінчується в позиції $i$ і збігається з префіксом. Але у нашому випадку це $\pi[i]$ — фактично довжина найбільшого блоку збігу з рядком $s$, що закінчується в позиції $i$. Більшою за $n$ ця довжина бути не може — завдяки роздільнику. А от рівність $\pi[i] = n$ (там, де вона досягається), означає, що в позиції $i$ закінчується шукане входження рядка $s$ (тільки не треба забувати, що всі позиції відлічуються у склеєному рядку $s+\#+t$).

Таким чином, якщо в деякій позиції $i$ виявилося $\pi[i] = n$, то в позиції $i - 2n$ рядка $t$ починається наступне входження рядка $s$ у рядок $t$.

Як уже згадувалося при описі алгоритму обчислення префікс-функції, якщо відомо, що значення префікс-функції не перевищуватимуть деякої величини, то достатньо зберігати не весь рядок і префікс-функцію, а лише її початок. У нашому випадку це означає, що потрібно зберігати в пам'яті лише рядок $s + \#$ та значення префікс-функції на ньому, а потім уже зчитувати по одному символу рядок $t$ і перераховувати поточне значення префікс-функції.

Отже, алгоритм Кнута-Морріса-Пратта вирішує це завдання за $O(n+m)$ часу та $O(n)$ пам'яті.

Реалізація

TODO: add implementation.

Застосування

TODO: add applications.

Задачі

TODO: add problems.