week15-ZJM与纸条

题目描述：

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为模式串

#include<iostream>
#include<istream> 
#include<string>
#include<cstring>
#include<cstdio>
using namespace std;

char *str1 = new char[1000010];
char *str2 = new char[1000010];
int j;
int *Next =  new int[1000010];
void getNext(char ptr[],int len){
    //Next = new int[len];
    Next[0]=0;
    for(int i=1,j=0;i<len;i++){
        while(j && ptr[i]!=ptr[j]) j=Next[j-1];
        if(ptr[i]==ptr[j])  j++;
        Next[i]=j;
    }
}
int KMP( char str[],char ptr[]){
    int len1 = strlen(str);
    int len2 = strlen(ptr);
    int cnt=0;  //cnt记录成功匹配次数 
    getNext(ptr,len2);
    for(int i=0,j=0;i<len1;i++){
        while(j && str[i]!=ptr[j])  j=Next[j-1];
        if(str[i]==ptr[j]) j++;
        if(j == len2){    //匹配到模式串末尾 
            cnt++;
            j = Next[j-1];   //根据Next数组转移 
        }
    } 
    return cnt; 
}            

int main(){
    
    std::ios::sync_with_stdio(false);
    int n;cin>>n;
    while(n--){
        cin>>str1;
        cin>>str2;
        int ans = KMP(str2,str1);
        cout<<ans<<endl; 
    }
    
    return 0;
}