Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП)
Функция примерно такая:
// простой поиск образца в строке
// возвращает индекс начала образца в строке или -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 |
Возьмем символ с номером 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 | 0 | 1 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 2 | 3 | 4 | 5 | 3 | 4 | 5 | 2 | 3 |
Префикс-функция
А теперь примеры префикс-функции. Отличие от описания выше в том, что, как принято в Си-языках, индексы считаются с 0.
Пример на C++
Функция возращает вектор длин префиксов строк, а строка передается как string (не надо вычислять длину)
vector prefix_function (string s) {
int n = (int) s.length();
vector pi (n); // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для построки длины i.
// p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых
for (int i=1; i 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 0) && (s[i] != s[j])) // не равны
j = pi[j-1]; // берем ранее рассчитанное значение (начиная с максимально возможных)
if (s[i] == s[j]) // равны
++j;
pi[i] = j;
}
}
Мой рассказ о маленьком чуде — алгоритме КМП подошел к концу. Конечно, эта статья о КМП далеко-далеко не первая и наверняка не последняя. Вот две статьи здесь, на хабрахабр: Поиск подстроки. Алгоритм Кнута–Морриса-Пратта и Поиск подстроки и смежные вопросы.
Но я надеюсь, кто-то посчитает эту статью полезной для себя, а кто-то (ведь может такое случиться) станет применять КМП.
Алгоритм КМП не единственный быстрый алгоритм поиска, но он достаточно быстрый (для задач типа олимпиадных) и при этом простой. В некоторых случаях алгоритм Ахо — Корасик может оказаться эффективней. Но те, кому действительно нужен это алгоритм, не нуждаются в популярном изложении, имхо.
Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях:
Комментарии (2)
6 августа 2016 в 15:44
0↑
↓
Я не понимаю, почему в таблице в разделе «Переходим к трюку» на позиции 6 (там где '@') стоит 3, а на позиции 8 стоит 5 как будто там найдено совпадение. Нет ли там ошибки?
6 августа 2016 в 15:54
0↑
↓
Спасибо за замечание — это проблемы копипаста. Так канительно создавать таблицы. Особенно с цветным выделением, т.к. оно сильно отвлекает внимание. Вроде сейчас поправил.
