KMP算法解决的问题是，在暴力匹配时文本指针不需要回退。基本思想就是当出现不匹配时，就能知晓一部分文本的内容（因为在匹配失败之前它们已经和模式相匹配）。我们可以利用这些信息避免将指针回退到所有这些已知的字符之前。
正文——A B A A A A B A A A A A A A A
模式——B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
模式—— B A A A A A
如果是暴力匹配的话，指针需要移动6次，但是可以看出其实不需要移动这么多次。
正文——A B A A A A B A A A A A A A A
模式—— B A A A A A
模式—— B A A A A A
提前判断如何重新开始查找，而这种判断只取决于模式本身。我们通过确定有限状态自动机（DFA）。模式中的每个字符都对应着一个状态，每个此类状态都能转换为字母表中的任意字符。
和模式字符串ABABAC对应的确定有限状态自动机
package chapter5;
/**
* Created by Blue on 2017/9/4.
*/
public class KMP {
private String pat;
private int[][] dfa;
public KMP(String pat) {
this.pat = pat;
int M = pat.length();
int R = 256;
dfa = new int[R][M];
dfa[pat.charAt(0)][0] = 1;
for (int X = 0, j = 1; j < M; j++) {
for (int c = 0; c < R; c++) {
dfa[c][j] = dfa[c][X];
}
dfa[pat.charAt(j)][j] = j + 1;
X = dfa[pat.charAt(j)][X];
}
}
public int search(String txt) {
int i, j, N = txt.length(), M = pat.length();
for (i = 0, j = 0; i < N && j < M; i++)
j = dfa[txt.charAt(i)][j];
if (j == M) return i - M;
else return N;
}
public static void main(String[] args) {
String pat = "ABABAC";
String txt = "BCBAABACAABABACAA";
KMP kmp = new KMP(pat);
System.out.println(txt);
int offset = kmp.search(txt);
for (int i = 0; i < offset; i++)
System.out.print(" ");
System.out.println(pat);
}
}
