2

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

Вот тут нашел реализацию на 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); - какой смысл выполнять префикс-функцию для образца?

3 ответа 3

2

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

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

6
  • Что именно непонятно? В "наивном" алгоритме образец перемещается по шаблону на постоянный шаг, равный 1. В КМП, используя префикс-функцию, мы можем перемещаться на большие шаги, гарантируя, что вхождение строки не будет пропущено.
    – DarkGenius
    28 окт 2014 в 13:34
  • @thejadefalcon, разумеется, в тривиальных случаях, когда образец состоит из разных символов, КМП будет работать даже медленнее "наивного" алгоритма. Но если образец имеет префикс-функцию, не состоящую из одних нулей, алгоритм будет работать быстрее за счет минимизации количества сравнений.
    – DarkGenius
    28 окт 2014 в 16:45
  • @DarkGenius Вот вы всё отвечаете и отвечаете, но никак не объясните, почему делается префикс функция для образца а не для образец#строка?)
    – user17711
    28 окт 2014 в 18:28
  • @thejadefalcon, потому что мы перемещаем образец по строке. Вы понимаете, для начала, примитивный алгоритм поиска подстроки? В нем мы сначала проверяем сопоставление образца и части строки, начиная с первого символа, затем со второго и т.д., пока вся строка будет пройдена. В случае нетривиальной префикс-функции образца мы избежим лишних сравнений, поскольку сможем сдвигать образец не на 1 символ, а на несколько.
    – DarkGenius
    29 окт 2014 в 5:09
  • Извините.. но Не понято
    – user17711
    29 окт 2014 в 7:42
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?

3
  • Неужели нет ответа на мой вопрос
    – user17711
    28 окт 2014 в 14:07
  • Ну так опять же. Зачем вообще сравнивать строку с образцом, если префикс функция для образец#строка все уже сделала сама? :)
    – user17711
    28 окт 2014 в 14:44
  • @avp Тогда теперь не пойму, как КМП использует префикс-функцию. Ну вот. Thebrownfoxjumpoverdog. Ищется образец "jump". Выполняется префикс-функция для "jump" = 0 0 0 0. И как это поможет?
    – user17711
    28 окт 2014 в 14:55

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.