KMP

输入两个字符串，一个模式串，一个主串，找出主串中含有多少段模式串
样例输入：

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

样例输出：

1
3
0

典型KMP算法题，KMP的难点在于next数组，顺利在模式串中初始化next数组也就成功一大半了。getnext（）函数说白了就是找相同的最长前缀和最长后缀的长度，比如abcab的最长相同前缀后缀是ab，就是2

下图中的1，2，3，4是一样的。1-2之间的和3-4之间的也是一样的，我们发现A和B不一样；之前的算法是我把下面的字符串往前移动一个距离，重新从头开始比较，那必然存在很多重复的比较。现在的做法是，我把下面的字符串往前移动，使3和2对其，直接比较C和A是否一样。

import java.util.*;
import java.io.*;
public class Main {
    static int nextt[];
    public static void main(String[] args){
        Scanner scan=new Scanner(System.in);
        int T=scan.nextInt();
        scan.nextLine();
        while(T-->0){
            String sstr=scan.nextLine();
            String lstr=scan.nextLine();
            nextt=new int[sstr.length()];
            getnext(nextt,sstr);
            kmp(sstr,lstr);
        }
    }

    public static void getnext(int nextt[],String str){
        int k=-1;
        nextt[0]=-1;//next[0]初始化为-1，-1表示不存在相同的最大前缀和最大后缀
        for(int i=1;i<str.length();i++){
            while(k>-1&&str.charAt(k+1)!=str.charAt(i))//如果下一个不同，那么k就变成next[k]，注意next[k]是小于k的，无论k取任何值。
                k=nextt[k];//往前回溯
            if(str.charAt(k+1)==str.charAt(i))
                k=k+1;//如果相同k++
            nextt[i]=k;//这个是把算的k的值（就是相同的最大前缀和最大后缀长）赋给nextt[i]
        }
    }

    public static void kmp(String shortstr,String longstr){
        int ans=0;
        int k=-1;
        for(int i=0;i<longstr.length();i++){//kmp的好处就是i不用回溯
            while(k>-1&&shortstr.charAt(k+1)!=longstr.charAt(i))//shortstr和longstr不匹配，且k>-1（表示shortstr和longstr有部分匹配）
                k=nextt[k];  //回溯
            if(shortstr.charAt(k+1)==longstr.charAt(i)){
                k=k+1;  //与getnext（）函数差不多
            }
            if(k==shortstr.length()-1){  //k移动到模式串最末端
                k=nextt[k];   //往前走
                ans++;  //匹配成功+1
            }
        }
        System.out.println(ans);
    }
}

这个是别人写的比较容易理解的博客
https://blog.csdn.net/starstar1992/article/details/54913261/