ZJM 的女朋友是一个书法家，喜欢写一些好看的英文书法。有一天 ZJM 拿到了她写的纸条，纸条上的字暗示了 ZJM 的女朋友 想给 ZJM 送生日礼物。ZJM 想知道自己收到的礼物是不是就是她送的，于是想看看自己收到的礼物在纸条中出现了多少次。
Input
第一行输入一个整数代表数据的组数
每组数据第一行一个字符串 P 代表 ZJM 想要的礼物, 包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 并且字符串长度满足 1 ≤ |P| ≤ 10,000 (|P| 代表字符串 P 的长度).
接下来一行一个字符串 S 代表 ZJM 女朋友的纸条, 也包含英语字符 {‘A’, ‘B’, ‘C’, …, ‘Z’}, 满足 |P| ≤ |S| ≤ 1,000,000.
Output
输出一行一个整数代表 P 在 S中出现的次数.
Sample Input
3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN
1
2
3
4
5
6
7
Sample Output
1
3
0
1
2
3
思路：
KMP算法直接用
KMP的精髓在于子模式串的匹配，即next数组的计算。
利用next数组可以避开明显不可能匹配的情况，降低时间复杂度。
时间复杂度：O（mn）---->O(n) //m为模式串
1 #include<iostream> 2 #include<istream> 3 #include<string> 4 #include<cstring> 5 #include<cstdio> 6 using namespace std; 7 8 char *str1 = new char[1000010]; 9 char *str2 = new char[1000010]; 10 int j; 11 int *Next = new int[1000010]; 12 void getNext(char ptr[],int len){ 13 //Next = new int[len]; 14 Next[0]=0; 15 for(int i=1,j=0;i<len;i++){ 16 while(j && ptr[i]!=ptr[j]) j=Next[j-1]; 17 if(ptr[i]==ptr[j]) j++; 18 Next[i]=j; 19 } 20 } 21 int KMP( char str[],char ptr[]){ 22 int len1 = strlen(str); 23 int len2 = strlen(ptr); 24 int cnt=0; //cnt记录成功匹配次数 25 getNext(ptr,len2); 26 for(int i=0,j=0;i<len1;i++){ 27 while(j && str[i]!=ptr[j]) j=Next[j-1]; 28 if(str[i]==ptr[j]) j++; 29 if(j == len2){ //匹配到模式串末尾 30 cnt++; 31 j = Next[j-1]; //根据Next数组转移 32 } 33 } 34 return cnt; 35 } 36 37 int main(){ 38 39 std::ios::sync_with_stdio(false); 40 int n;cin>>n; 41 while(n--){ 42 cin>>str1; 43 cin>>str2; 44 int ans = KMP(str2,str1); 45 cout<<ans<<endl; 46 } 47 48 return 0; 49 }
原文：https://www.cnblogs.com/liuzhuan-xingyun/p/13049147.html