Алгоритм Кнута-Моррса-Пратта используется для поиска подстроки (образца) в строке. Кажется, что может быть проще: двигаемся по строке и сравниваем последовательно символы с образцом. Не совпало, перемещаем начало сравнения на один шаг и снова сравниваем. И так до тех пор, пока не найдем образец или не достигнем конца строки.
Функция примерно такая:
// простой поиск образца в строке
// возвращает индекс начала образца в строке или -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.
Теперь другой случай — 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 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 3 |
Символ '@' играет роль разделителя, его заведомо нет ни в образце, ни в строке поиска (нужно подобрать именно такой символ). Посмотрим на позиции 11, 14, 16, 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 pi;
}
Пример на C
Функция ничего не возвращает. Первый параметр — указатель на строку, второй — указатель на заполняемый массив длин префиксов, третий р — длина строки и массива.
void prefix_function (char *s, int *pi, 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;
}
}
Мой рассказ о маленьком чуде — алгоритме КМП подошел к концу. Конечно, эта статья о КМП далеко-далеко не первая и наверняка не последняя. Вот две статьи здесь, на хабрахабр: Поиск подстроки. Алгоритм Кнута–Морриса-Пратта и Поиск подстроки и смежные вопросы.
Но я надеюсь, кто-то посчитает эту статью полезной для себя, а кто-то (ведь может такое случиться) станет применять КМП.
Алгоритм КМП не единственный быстрый алгоритм поиска, но он достаточно быстрый (для задач типа олимпиадных) и при этом простой. В некоторый случаях алгоритм Ахо — Корасик может оказаться эффективней. Но те, кому действительно нужен это алгоритм, не нуждаются в популярном изложении, имхо.
Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях:
Автор: zelserg
