# KMP 算法

KMP算法用于字符串的模式匹配，也就是查找某个字符串里是否存在某个子串，并返回位置，也就是Java/C++里的String.indexOf()方法。  字符串匹配最朴素的算法就是一个一个去比较，出错了就回溯到下一个起点继续比较。这样的复杂度有O(mn)，即原字符串×匹配串。而KMP算法能把时间复杂度降到O(m+n)。KMP这个缩写来自于Knuth，Morris和Pratt，瞬间想到了AVL树。

• Source串(Target)：              a b a b a b a b a c b
• 匹配串(Pattern)：                a b a b a c b
• 根据Pattern得出的数组F:  0 0 0 1 2 3 0  (P怎么计算的后面会讲)  数字代表如果这次mismatch需要回到退几位

```/** * Knuth-Morris-Pratt Algorithm for Pattern Matching */
public class KMPMatch {

private String text;
private String pattern;
private int[] failure;
private int matchPoint;

...
/** * Finds the first occurrence of the pattern in the text. */
public boolean match() {
int j = 0;
if (text.length() == 0) return false;

for (int i = 0; i < text.length(); i++) {
// p1: only execute when previous match is found and mismatch happend
while (j > 0 && pattern.charAt(j) != text.charAt(i)) {
j = failure[j - 1];
}
//p2: this p2 always execute before p1
if (pattern.charAt(j) == text.charAt(i)) { j++; }
if (j == pattern.length()) {
matchPoint = i - pattern.length() + 1;
return true;
}
}
return false;
}
/** * Computes the failure function using a boot-strapping process, * where the pattern is matched against itself. */
private void computeFailure() {
int j = 0;
for (int i = 1; i < pattern.length(); i++) {
while (j > 0 && pattern.charAt(j) != pattern.charAt(i)) {
j = failure[j - 1];
}
if (pattern.charAt(j) == pattern.charAt(i)) {
j++;
}
failure[i] = j;
}
}
...
}```