понедельник, 31 октября 2011 г.

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

                         По мотивам лекции Сагунова Данила и реализации 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 – Поиск подстроки

1 комментарий:

  1. спасибо за отличный пост, постараюсь найти время, чтобы поразбираться в этом! Но вроде не так всё сложно :)

    ОтветитьУдалить