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

в 12:22, , рубрики: C, c++, алгоритм Кнута-Морриса-Пратта, Поиск строки, метки: ,

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

Функция примерно такая:

// простой поиск образца в строке
// возвращает индекс начала образца в строке или -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;
     }
} 

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

Алгоритм КМП не единственный быстрый алгоритм поиска, но он достаточно быстрый (для задач типа олимпиадных) и при этом простой. В некоторый случаях алгоритм Ахо — Корасик может оказаться эффективней. Но те, кому действительно нужен это алгоритм, не нуждаются в популярном изложении, имхо.

Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях:

Иллюстрации

Это маленькое чудо — алгоритм Кнута-Морриса-Пратта (КМП) - 1

Автор: zelserg

Источник

Поделиться новостью

* - обязательные к заполнению поля