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

Рейтинг: 2Ответов: 3Опубликовано: 28.10.2014

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

Вот тут нашел реализацию на Java: https://sites.google.com/site/indy256/algo/kmp_matcher
И мне не понятно это:

public static int kmpMatcher(String s, String pattern) {
int m = pattern.length();
if (m == 0)
  return 0;
int[] p = prefixFunction(pattern);
for (int i = 0, k = 0; i < s.length(); i++)
  for (; ; k = p[k - 1]) {
    if (pattern.charAt(k) == s.charAt(i)) {
      if (++k == m)
        return i + 1 - m;
      break;
    }
    if (k == 0)
      break;
  }
return -1;
}

int[] p = prefixFunction(pattern); - какой смысл выполнять префикс-функцию для образца?

java алгоритм
Источник: Stack Overflow на русском

Ответы

▲ 2

Вычисление префикс-функции образца позволит избежать лишних сравнений.

Я как-то писал статью, в которой старался понятным языком объяснить принцип работы алгоритма. Надеюсь, она поможет Вам внести ясность в понимание алгоритма.

▲ 1

К примеру, строка S=123123123, мы ищем вхождение сроки n=123123.
Если идти в лоб, то мы в цикле будем каждый раз смещаться по строке S на 1 и брать ее срез длине строке n и производить сравнение.

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

▲ 1

Префикс-функция (prefixFunction()) транслирует строковый образец в представление (массив индексов в строковом образце), удобное для быстрого определения, находится ли целый образец в данном месте строки.

Смотрите, kmpMatcher() в цикле перебирает все позиции s, и если в этой позиции присутствует образец, то возвращает ее (результат -- FOUND).

А если бы нам было нужно искать один и тот же образец во многих строках, то было бы выгодней вычислить prefixFunction один раз и передавать ее результат вместе с проверяемой строкой в модифицированный kmpMatcher(String s, int [] pattern).

Обновление

Да, в самом деле. Я теперь тоже не понимаю.

--

Кажется, понял. В соответствии с описанием в вики (просто и доходчиво) при несовпадении очередного символа строки мы начнем новые сравнения не обязательно с первого символа образца.

Именно p[] (его вычисляет prefixFunction) определяет, с какого.

Обновление 2

Для экономии памяти. Представьте строку размером 100 мегабайт и образец в 100 байт.

Вы предлагаете вычислять префикс-функцию для 100 MB?