假设有两个字符串，一个长字符串，一个短字符串，我们想要知道在这个长字符串中是否包含这个短字符串，就需要在长字符串中搜索短字符串。那么我们最容易想到的方法是什么呢，就是暴力法：
public void main(){
//a为长字符串
String a = "ababababaab";
//b为短字符串
String b = "babaa";
for(int i = 0; i < a.length(); i++){
for(int j = 0; j < b.length(); j++){
if(a.charAt(i+j) != b.charAt(j)) break;
if(j == b.length()-1) System.out.println("匹配字符串的初始下标为：" + i);
}
}
}
上述方法为解决该问题的暴力法时间复杂度为O(m*n),mn为两个字符串的长度。该时间复杂度是比较高的，所以有很多人苦思冥想，最终想出了KMP法来解决这个问题
KMP利用了短字符串的一些性质，避免了大部分错误的枚举。如下图所示，在第一次搜索时搜索到了绿色的位置，发现不匹配，这个时候，如果按照暴力法，那么会变成图2中显示的情况。再开始匹配，但是我们知道因为绿色之前的字符串是已经匹配了的，而绿色之后的字符串是不匹配的，这个时候短字符串还想匹配到图1中绿色的位置，假设短字符串现在匹配到了长字符串的第4位和短字符串的第4位，在第五位的时候不匹配了，那么短字符串向后移动一位之后，如果短字符串能与长字符串匹配到绿色的的位置也就是，长字符串的2，3，4位匹配短字符串的1，2，3位，那么这次枚举才是有意义的，不然这次枚举就是没有必要的，肯定会失败。
那么，我们通过短字符串自身的性质就可以判断出该次枚举是否有必要，我们知道第一次循环长字符串的1，2，3，4位和短字符串的1，2，3，4位匹配，在第5位不匹配，我们发现长字符串的2，3，4位就是对应的短字符串的1，2，3位，也就是说只有短字符串的1，2，3位对应短字符串的2，3，4位这次枚举就是有效的，否则就是无效的，我们可以来判断是否满足这个性质，如果满足这个性质，那么就进行这次枚举，如果不满足这个性质，就不进行这次枚举，那么我们接着来看下一次枚举，假如说字符串又向右移动了一位，这次长字符串的3，4位对应的短字符串的1，2位，而长字符串的3，4位有和短字符串的3，4位在图1中匹配，所以我们转换得到如果短字符串的1，2位和短字符串的3，4位是相同的，那么该次枚举就是有效的，否则就是无效了，也就是说，当我们知道在字符串的前i位构成的字串中，我们事先知道每一个字串中的前缀与后缀的的字符相等的最大长度，那么就可以避免很多不必要的枚举。现在假设我们已经知道了上述前缀与后缀相等的最大长度，我们看一下我们的代码会发生什么变化。
这里我们定义next数组代表字符串前i位所组成的字串的前缀与后缀相等的最大长度。
public void main(){
//a为长字符串
String a = "ababababaab";
//b为短字符串
String b = "babaa";
//这里短字符串的第j位如果不匹配，那么我们首先要访问第j-1位的上述最大长度。
//得到了最大长度之后我们就可以将让i直接向前移动j-1-next[j-1]。
//j变为next[j-1],这样我们就避免了不必要的枚举
//通过考虑边界值之后，我们发现我们的代码变成了这样
for(int i=0, j=0 ; i < a.length(); i++){
//这里把j移到外面是因为我们通过next数组来设置j，而next数组的第0位就是0，如果我们短字符串第一位就匹配不上，那么我们需要将i++，然后重新匹配。
for(;; j++){
if(i+j >= a.length()) break;
if(a.charAt(i+j) != b.charAt(j)) {
if( j != 0){
i = i + j-1-next[j-1];
j = next[j-1];
}else break;
}
if(j == b.length()-1) {
System.out.println("匹配字符串的初始下标为：" + i);
i = i + j-1-next[j-1];
j = next[j];
break;
}
}
}
}
上述代码中i表示长字符串起始位置，j表示短字符串未匹配将要匹配的下标，我们现在改变定义，另i表示长字符串的未匹配但是将要匹配的下标，j表示短字符串未匹配将要匹配的下标，我们看看代码会发生什么变化：
public void main(){
//a为长字符串
String a = "ababababaab";
//b为短字符串
String b = "babaa";
for(int i=0, j=0 ; i < a.length(); i++){
for(;;){
if(a.charAt(i) != b.charAt(j)) {
if( j != 0){
//这里如果i表示的未匹配但是将要匹配的值，那么我们有图1可以发现，在短字符串移动后，我们还是将长字符串的第5个字符和短字符串进行匹配，所以i在这里不变
j = next[j-1];
}else break;
}
if(a.charAt(i) == b.charAt(j)){
if(j == b.length()-1) {
System.out.println("匹配字符串的初始下标为：" + i-j);
j = next[j];
}else {
j++;
}
break;
}
}
}
}
这里我们发现除了if(a.charAt(i) != b.charAt(j) && j != 0)这种情况，其他情况都会跳出死循环。于是我们只需要将循环添加到该判断语句就可以。整理代码可得
public void main(){
//a为长字符串
String a = "ababababaab";
//b为短字符串
String b = "babaa";
for(int i=0, j=0 ; i < a.length(); i++){
while(j!=0 && a.charAt(i) != b.charAt(j)) {
j = next[j-1];
}
if(a.charAt(i) == b.charAt(j)){
if(j == b.length()-1) {
System.out.println("匹配字符串的初始下标为：" + i-j);
j = next[j];
}else {
j++;
}
}
}
}
现在这样就是比较常见的KMP算法的代码了。
在上面的算法中，我们在以知next数组的情况下，了解到KMP算法的步骤，下一步我们将来寻找一个求解next数组的方法。
我们发现求解next数组可以采用动态规划与KMP的思想。
我们把字串的后缀当作上述长字符串，子串的前缀当作上述短字符串，于是，我们设定初始条件next[0] = 0;
next[0] = 0;
//i代表后缀的最后一位，j代表前缀（不是最后一位）。
for(int i = 1,j = 0;i < b.length(); i++){
if(b.charAt(i) == b.charAt(j)){
next[i] = next[i-1]+1;
j++;
}else{
while(j != 0 && b.charAt(i) != b.charAt(j)) j = next[j-1];
if(j == 0 &&b.charAt(i) != b.charAt(j)) next[i] = 0;
else if(j == 0) next[i] = 1;
else next[i] = next[j-1]+1;
}
}
下面是KMP比较简单的写法，方便记忆，背会就对了
import java.util.*;
class Main{
public static void main(String[] args){
int ne[] = new int[10010];
ne[0] = -1;
Scanner Reader = new Scanner(System.in);
int n = Reader.nextInt();
String s = Reader.next();
int m = Reader.nextInt();
String c = Reader.next();
//求next数组
for(int i = 1,j = -1; i < n; i++){
while(j >=0 && s.charAt(i) != s.charAt(j+1)) j = ne[j];
if(s.charAt(i) == s.charAt(j+1)) j++;
ne[i] = j;
}
for(int i = 0,j = -1; i < m; i++){
while(j >=0 && c.charAt(i) != s.charAt(j+1)) j = ne[j];
if(c.charAt(i) == s.charAt(j+1)) j++;
if(j == n-1) {
System.out.print(i-j+" ");
j = ne[j];
}
}
}
}