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

                         По мотивам лекции Сагунова Данила и реализации indy256

Алгоритм относится к разряду алгоритмов поиска подстроки в строке.

Префиксом строки S называется подстрока строки S, первый символ которой совпадает с первым символом строки S.
Суффиксом строки S называется подстрока строки S, последний символ которой совпадает с последним символом строки S.
Длина префикса и суффикса строки S строго меньше длины строки S.
Префикс функция от строки S: П(S) – это максимальная длина префикса S, совпадающего с её суффиксом.
Z-функция от строки S – это массив длинной равной длине строки S, где Z[i] – это префикс функция от подстроки S, последний символ, которой равен S[i].

Пусть S = “abababaaabababac”
z[0]  = П(“a”)                = 0
z[1]  = П(“ab”)               = 0 
z[2]  = П(“aba”)              = 1
z[3]  = П(“abab”)             = 2
z[4]  = П(“ababa”)            = 3
z[5]  = П(“ababab”)           = 4
z[6]  = П(“abababa”)          = 5
z[7]  = П(“abababaa”)         = 1
z[8]  = П(“abababaaa”)        = 1
z[9]  = П(“abababaaab”)       = 2
z[10] = П(“abababaaaba”)      = 3
z[11] = П(“abababaaabab”)     = 4
z[12] = П(“abababaaababa”)    = 5
z[13] = П(“abababaaababab”)   = 6
z[14] = П(“abababaaabababa”)  = 7
z[15] = П(“abababaaabababac”) = 0

Можно заметить, что z-функция может увеличиваться за один шаг не более чем на 1, а уменьшиться на произвольное количество.

1. void prefix_func(const string &str, vector<int> &z) {
2.  
3.   z.resize(str.size());
4.   z[0] = 0;
5.   for (int i=1;i<z.size();++i) {
6.     int pos = z[i-1];
7.     while (pos > 0 && str[pos] != str[i])
8.       pos = z[pos-1];
9.     z[i] = pos + (str[pos] == str[i] ? 1 : 0);
10.   }
11. }

* This source code was highlighted with Source Code Highlighter.

Ключевым моментов в функции подсчета Z-функции является цикл while(7-8 строки). На каждом шаге пытаемся увеличить длину префикса, равного суффиксу. Если это сделать не удается, то необходимо уменьшить размер префикса максимальным образом.

Рассмотрим нахождение z[7]. Текущая подстрока “abababaa”, z[6] = 5.
На шаге 7 пытаемся продолжить увеличивать длину префикса.
1) Сравниваем 5-ый символ с последним: ”abababaa”
2) Необходимо максимальным образом уменьшить длину префикса. Для этого нужно найти префикс префикса, который обязательно будет равен суффиксу суффикса. П(”ababa”) = 3
3) Сравниваем 3-ый символ с последним: “abababaa”. Продолжаем рассуждения пока префикс существует, т.е. пока имеет ненулевую длину, либо до совпадения концов префикса и суффикса. П(“aba”) = 1.
4) Сравниваем 1-ый символ с последним: “abababaa”. П(“a”) = 0.
5) Сравниваем 0-ой символ с последним: “abababaa”. Успех =)
Значит z[7] = 1.

Вернемся к исходной задаче поиска подстроки(S) в строке(TEXT). Если не хочется заморачиваться, а главное если есть такая возможность, то в общем случае можно получить строку TEXT’ = S + sep + TEXT, где sep – это символ, который гарантированно не встречается в строках S и TEXT, а “+” – это конкатенация строк. Затем найти z-функцию от TEXT’. Если z[i] = длина(S), значит S является подстрокой строки TEXT.

1. void kmp() {
2.   text = str + "#" + text;
3.   z.resize(text.size(), -1);
4.  
5.   z[0] = 0;
6.   for (int i=1;i<text.size();++i) {
7.     int pos = z[i-1];
8.     while (pos != -1 && text[i] != text[pos])
9.       pos = pos - 1 >= 0 ? z[pos-1] : -1;
10.     z[i] = pos + 1;     
11.   }
12. }
13. void output() {
14.   for (int i=0;i<text.size();++i) {
15.     if (z[i] == str.size()) {
16.       cout<< i - 2*str.size() <<' ';
17.     }
18.   }
19. }

* This source code was highlighted with Source Code Highlighter.

Понятно, что в данной реализации происходит лишнее выделение памяти, и не всегда есть возможность вести себя так вальяжно.

Более эффективная реализация:

1. void prefix_func(const string &str, vector<int> &z) {
2.  
3.   z.resize(str.size());
4.   z[0] = 0;
5.   for (int i=1;i<z.size();++i) {
6.     int pos = z[i-1];
7.     while (pos > 0 && str[pos] != str[i])
8.       pos = z[pos-1];
9.     z[i] = pos + (str[pos] == str[i] ? 1 : 0);
10.   }
11. }
12. void kmp(const string &text, const string &str) {
13.   vector<int> z;
14.   prefix_func(str,z);
15.   int pos = 0;
16.   for (int i=0; i<text.size(); ++i) {
17.     while (pos > 0 && (pos >= str.size() || str[pos] != text[i]) )
18.       pos = z[pos-1];
19.     if (text[i] == str[pos]) pos++;
20.     if (pos == str.size())
21.       printf("%d ", i - pos + 1);
22.   }
23. }

* This source code was highlighted with Source Code Highlighter.

Здесь сначала считается z-функция для строки S, а потом происходит эмуляция первой реализации, как будто строка S является префиксом строки TEXT. Как видно в данном случае затраты на память сократятся.

Попрактиковаться можно здесь:
spoj.pl - NHAY 
acmp.ru – Поиск подстроки