参考链接： http://wiki.jikexueyuan.com/project/kmp-algorithm/define.html 图解 https://www.cnblogs.com/yjiyjige/p/3263858.html 代码
KMP要解决的问题是字符串匹配
输入：一个文本串S，和一个模式串P 输出：若干行，每行包含一个整数，表示s2在s1中出现的位置
详细原理参考上述链接，我自己对着写了一套代码
public static void main(String[] args) { KMP kmp = new KMP(); String s = "ABACDABABC"; int[] next = kmp.getNext(s); for(int i : next){ System.out.print(i+" "); } String p = "ACD"; System.out.println(kmp.find(s,p)); } //next 数组获取 public int[] getNext(String s){ int len = s.length(); int[] next = new int[len]; next[0] = -1; int k = -1; int j = 1; while(j<len-1){ if(k==-1 || s.charAt(j)==s.charAt(k)){ //匹配时，向后推进 next[++j] = ++k; } else{ //不匹配时，当前已经匹配的字符串子匹配，递归 k = next[k]; } } return next; } //字符串查找的具体实现 public int find(String str,String p){ int len1 = str.length(); int len2 = p.length(); int[] next = getNext(p); int i=0,j=0; while(i<len1 && j<len2){ if(j==-1 || str.charAt(i) == p.charAt(j)){ ++i; ++j; } else{ j = next[j]; } } if(j==len2){ return i-j; } else{ return -1; } }