[week15] C - ZJM与纸条（选做）—— KMP算法

题意

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中出现的次数.

输入样例

3
BAPC
BAPC
AZA
AZAZAZA
VERDI
AVERDXIVYERDIAN

输出样例

1
3
0

提示

分析

这也是一道用KMP算法解决的字符串问题。

• KMP算法

1. KMP算法的作用

KMP算法是用来求一个字符串在另一个字符串中出现的次数，或是所有出现的位置。

如：abbabab中bab出现的次数为2。分别为第3-5个字符和第5-7个字符。显然子串在字符串中出现的不同位置可以有部分重复。

其中用来匹配的子串被称作模式串，被匹配的长字符串为主串。

2. next数组

next数组是实现KMP算法的关键。

next[i]存储的是字符串中从开头到下标为i的这一段子串中，首尾相同字符串的长度。

如，abcabc：

• 在该字符串中，第一个字符（下标为0）到倒数第二个字符（下标为4）这一段的字符串中，首尾存在相同的字符串ab，因此next [4] = 2
• 第一个字符（下标为0）最后一个字符（下标为5）这一段的字符串中，首尾存在相同的字符串abc，因此next [5] = 3
• 其余部分构成的字符串中，首尾都不存在相同部分，因此都为0。

3. KMP算法

算法过程如下：

• 从主串和模式串的首部开始依次扫描每一个字符
• 若当前主串扫描的字符和模式串扫描的字符相同，则模式串指针后移
• 若当前二者扫描的字符不同，则开始转移：
  • 主串指针不变
  • 模式串的指针从当前匹配失败处转移为指向下标等于当前指向字符的前一个字符所对应的next数组中存储长度的字符
  • 循环转移，直到回到模式串首部，或转移后指针指向字符与主串指向字符匹配成功
• 若模式串被扫描完，则说明已经在主串中找到一个模式串，出现次数+1或执行对应操作
• 主串指针后移

4. 求next数组

next数组完全可以用KMP算法求得。也就是模式串自己匹配自己来获得next数组。

从模式串的第一个和第二个字符开始匹配，即主串从第二哥字符开始扫描，模式串从第一个字符开始。因为对第一个字符来说不存在首尾部分。

在这个匹配过程中，模式串和主串相同。其中模式串扫描的部分就相当于是原字符串中的首部分，而被匹配的主串与模式串所匹配的部分就是原字符串中的尾部分。

也就是用字符串每一个首部分与其每一个尾部分匹配（首尾部分最长就为前半部分和后半部分），来得到第一个字符开始到每一个字符结尾所构成的字符串中的首尾相同子串的长度。

next的使用原理：

假设主串和模式串中第 i 个字符匹配失败，若next[i] = p。
则第i个字符的前p个字符与模式串的前p个字符完全相同，那么将模式串移动，直到第i个字符的前p个字符与模式串前p个字符一一对应。
那么显然，接下来要从主串的第i个字符和模式串的第p + 1个字符开始继续进行匹配。

而模式串重新开始扫描字符在字符串数组的下标就等于p（若从下标为0处开始存储），因此next数组是用来重新定位模式串扫描起点的。

• 题目分析

这道题就是利用KMP算法解决。只要理解了KMP算法，就可以很好解决。这道题是用该算法求出现次数。

总结

1. 这个算法的难点在于理解next数组的计算过程。但是稍微思考一下还是没啥问题的。

代码

//
//  main.cpp
//  lab3
//
//

#include <iostream>
#include <string>
using namespace std;

int Next[10002];

void get_next(string s1,int length)     //得到next数组
{
    Next[0] = 0;
    
    for( int i = 1 , j = 0 ; i < length ; i++ )     //遍历模式串，自己与自己进行匹配
    {
        while( j && s1[i] != s1[j] )
            j = Next[j - 1];
        
        if( s1[i] == s1[j] )
            j++;
        
        Next[i] = j;
    }
}

int kmp(string s1,string s2)        //kmp
{
    int res = 0;
    
    get_next(s2,s2.size());     //得到模式串的next数组
    
    for( int i = 0,j = 0 ; i < s1.size() ; i++ )        //遍历主串
    {
        //若匹配失败
        //从模式串中当前匹配失败字符的前一个字符的next数组所对应的字符开始重新匹配
        while( j && s1[i] != s2[j] )
            j = Next[j - 1];
        
        //匹配成功，模式串向后扫描
        if( s1[i] == s2[j] )
            j++;
        
        //若模式串被完整扫描，则说明主串包含模式串
        if( j == s2.size() )
        {
            res++;                  //包含模式串的个数+1
            j = Next[j - 1];        //主串向后继续扫描
        }
    }
    return res;
    
}



int main()
{
    ios::sync_with_stdio(false);
    
    int t = 0;
    cin>>t;
    
    while( t-- )
    {
        string s1,s2;
        cin>>s2>>s1;
        
        cout<<kmp(s1, s2)<<endl;
    
    }
    
    return 0;
}