题目是这样的:给你T组数据,每组2个字符串A,B求A在B中出现次数(超过106个字符)

所以只能用KMP

简单介绍一下KMP(刚学)

在字符串匹配的过程中,若使用O(NM)暴力算法,显然会有很多多余匹配的操作。比如 匹配 aaaaaaaaaaaaab 和 aaaab。前面那么多 a 你就一个个挨着匹配不累啊。所以有了KMP算法。
KMP算法的主体思想是:利用NEXT数组在A,B的某一位匹配失败时主动将B串前移一定位数,跳过绝对不会出现匹配情况的串部分。而NEXT数组是什么呢?

NEXT[i]表示 待匹配串B的长度为i的前缀 的 长度相同且字符相同(说白了就是完全相同)的前缀和后缀的最长长度。

如对于 ababcaba : NEXT[3]=1 ,NEXT[4]=2 ,NEXT[5]=0 ,NEXT[8]=3...
这样,当如图的情况时,我们可以让B串前移NEXT[i-1]位

这样,我们就可以很快求出B是否为A的字串。

于是,现在最大的问题就是如何求NEXT数组

方法:若现在我们已经求出了NEXT[i],就会有如下的两种情况(注意NEXT下标为长度而B为字符串的位)
a. B[i]==B[NEXT[i]+1],此时NEXT[i+1]=NEXT[i]+1;
b. B[i]!=B[NEXT[i]+1],此时NEXT[i+1]可以由一种高深的方法得到:不断寻找B前i位的公共前后缀的公共前后缀...直到某一个前缀的后一位与B[i]相同,NEXT[i+1]={此时的NEXT};