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