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

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

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

Простой случай поиска'игла' — образец'стогистогстогигстогстогиглстогстогигластогигластог' — строка поискаСложный случай поискаaabbaabaabaabbaaabaabaabaabaabbaabbФункция работает и довольно шустро, если образцы и строка «хорошие». Хорошие — это когда внутренний цикл прерывается быстро (на 1-3 шаге, скажем, как в простом случае). Но если образец и строка содержат часто повторяющиеся вложенные куски (как сложном случае выше), то внутренний цикл обрывается ближе к концу образца и время поиска оценивается как О(<длина образца>*<длина строки>). Если длина строки 100тыс, а длина образца 100, то получаем О(10млн). Конечно, реально редко встретишь образец длиной 100, но в олимпиадных задачах «на поиск» это обычное дело, поэтому там простой поиск часто не подходит.А если строка — это длинный текст, а образец-фрагмент слова, и надо найти все вхождения этого фрагмента, причем на лету, по мере набора слова (замечали, как быстро это делают браузеры)? Алгоритм КМП находит все вхождения образца в строку и его скорость О(<длина образца>+<длина строки>), поэтому на больших текстах/образцах или на слабых процессорах (как в низкобюджетных сотовых) он вне конкуренции.А теперь посмотрим на заголовок? Почему «маленькое»? Потому, что изюминка КМП — это префикс-функция, а она действительно маленькая. А почему «чудо»? Потому что, он вроде как решает совсем другую задачу и это решение, после некоторого чудесного трюка, превращается в решение задачи поиска всех вхождений образца в строку.Для того, чтобы понять, что и как делает префиксная функция, посмотрим на сложную строкуСтрока под ней — номер (позиция) символа в строке (для удобства описания алгоритма считаем номер с 1), а самая нижняя строка- массив M длин префиксов, ключ к пониманию префикс-функции.Возьмем символ с номером 7 (это a) и для K от 1 до 6 рассмотрим строки-префиксы (подстрока, начинающаяся с первого индекса строки) и суффиксы (подстрока, последний символ которой в строке в позиции 7 ( это «наш» символ a) длины K.Обратите внимание: для длины 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=6 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 и вызовем для нее префикс-функцию для заполнения массива.Символ '@' играет роль разделителя, его заведомо нет ни в образце, ни в строке поиска (нужно подобрать именно такой символ). Посмотрим на позиции 11, 14, 19, 22 массива. Значения в массиве равны 5, это означает, что суффикс длиной 5 (фрагмент строки поиска) совпадает с 5 символами префикса. А 5 символов префикса — это и есть образец для поиска! Алгоритм поиска получатся такой — склеиваем с помощью разделителя образец и строку поиска, передаем «склейку» префиксной функции и потом ищем в массиве элементы, равные длине образца, Можно заметить, что значений больше длины образца не будет из-за символа-разделителя, а значения, равные длине образца могут появиться только в позициях, соотвествующих исходной строке поиска. Склеенная строка имеет длину <длина образца>+<длина строки>, поэтому время расчета оценивается как О(<длина образца>+<длина строки>), как и говорилось в начале статьи. Объем необходимого префикс-функции буфера равен <длина образца>+<длина строки>, но можно модифицировать префикс-функцию так, чтобы хватило буфера <длина образца> (пример модификации в дополнении)

Префикс-функция

А теперь примеры префикс-функции. Отличие от описания выше в том, что, как принято в Си-языках, индексы считаются с 0.

Пример на C++

Функция возвращает вектор длин префиксов строк, а строка передается как string (не надо вычислять длину)

vector<size_t> prefix_function (string s) 
{
    size_t n =  s.length();
    vector<size_t> pi(n); // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для подстроки длины i. 
			 // p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых 
    for (size_t i=1; i<n; ++i) 
    {
       // ищем, какой префикс-суффикс можно расширить
        size_t 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

Функция ничего не возвращает. Первый параметр — указатель на строку, второй — указатель на заполняемый массив длин префиксов, третий р — длина строки и массива.

// если компилятор не понимает size_t, замените на int
void prefix_function (char *s, int *pi, size_t n) 
{
     pi[0]=0;          // в i-м элементе (его индекс i-1) количество совпавших символов в начале и конце для подстроки длины i. 
	              // p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых 
     for (size_t 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;
     }
} 

Этот код добавлен по результатам обсуждения. Образец и строка поиска передаются в разных параметрах, т.е. их не надо «склеивать». Массив длин префиксов заполняется только для образца.

// пример функции обработки, которая выводит индекс начала найденного образца
int f(size_t i) 
{
    printf("%d\n",i);
    return 1;
}
// str строка поиска.
// obr образец, который ищем.
// pi массив длин префиксов для образца (минимум  сколько символов в образце).
// int f(size_t i) когда образец найден, вызывается эта функция, 
// ей передается индекс начала найденного в str образца.
// функция возвращает 0, если надо прекратить поиск и 1, если надо продолжить.
void prefix_find (char *str, char *obr, size_t *pi, int (*f)(size_t)) 
{
     pi[0]=0;     // в i-м элементе (его индекс i-1) количество совпавших 
                  // символов в начале образца и в конце подстроки длины i. 
                  // p[0]=0 всегда, p[1]=1, если начинается с двух одинаковых 
     size_t l;    // будет длина образца
     // заполняем массив длин префиксов для образца
     for (l=1; obr[l]; ++l) 
     {
        size_t j = pi[l-1];
        while ((j > 0) && (obr[l] != obr[j])) // не равны
            j = pi[j-1];	         // берем ранее рассчитанное значение (начиная с максимально возможных)
        if (obr[l] == obr[j])      // равны 
            ++j; 
        pi[l] = j;
     }
     size_t j=0; // количество совпавших символов, оно же индекс сравниваемого 
     // символа в образце. В строке сравниваемый символ будет иметь индекс i
     for (size_t i=0; str[i]; ++i) 
     {

это место — ключ к эффективности КМП. Если очередные символы строки и образца не совпали, мы не двигаем образец на 1 символ и не сравниваем его со строкой с самого начала (как в примитивном поиске в начале статьи). Мы сдвигаем образец на несколько символов и делаем одно сравнение str[i] и obr[j]. Если не совпало — опять сдвиг образца, пока символы не совпадут или не дойдем до начала образца. Т.о. по строке поиска назад не двигаемся, только вперед (хотя и с остановками).

        while ((j > 0) && (str[i] != obr[j])) 
// Очередной символ строки не совпал с символом в образце. Сдвигаем образец, 
// причем точно знаем, что первые j символов образца совпали с символами строки 
// и надо сравнить j+1й символ образца (его индекс j) с i+1м символом строки.
            j = pi[j-1];    // если j=0, то достигли начала образца и цикл следует прервать
                  
        if (str[i] == obr[j]) // есть совпадение очередного символа 
            ++j;              // увеличиваем длину совпавшего фрагмента на 1
        if (j==l)
            if (!f(i-l+1)) // образец найден, вызовем функцию обработки
                  return;  // и выйдем из процедуры, если она вернет 0. 
     }
} 

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

Дополнение по результатам обсуждения

Можно модифицировать префикс-функцию, чтобы она использовала буфер не О(длина строки+длина образца) а О(длина образца). В этом случае память нужно выделить только для хранения длин префиксов образца, а длины префиксов строки поиска не запоминаются в массиве. Длина для текущей позиции хранится в переменной и как только она сравнивается с длиной образца (т.е. образец найден), префикс-функция вызывает функцию обработки найденного фрагмента. Модифированная функция prefix_find добавлена в статью. Реально мне ни разу не потребовалось экономить на выделении памяти для массива, но не исключаю, что у кому-то может понадобиться.На возможность сэкономить память обратил мое внимание mayorovp и он же дал ссылку в своем сообщении на реализацию варианта префикс-функции, которая выводит позиции найденных фрагментов в cout. По замечанию staticlab изменил тип переменных на size_t (так действительно будет корректнее).Для тех, кто дочитал статью до конца, приведу иллюстрации, показывающие, как организованы префиксно-суффиксные блоки в достаточно сложных случаях: