目录

Oulipo (KMP 统计出现次数)

题目

求模式串在待匹配串中的出现次数。

Input

第一行是一个数字T，表明测试数据组数。之后每组数据都有两行：

第一行为模式串，长度不大于10,000；

第二行为待匹配串，长度不大于1,000,000。（所有字符串只由大写字母组成）

Output

每组数据输出一行结果。

Sample Input

4

ABCD

ABCD

SOS

SOSOSOS

CDCDCDC

CDC

KMP

SOEASY

Sample Output

1

3

0

0

题解及思路

就是直接KMP然后求出现次数。

注意的地方：

1. next 数组的范围，也就是循环结束的地方。
2. 可能会模式串是一位的情况。

#include 
    
     #include 
     
      #include 
      
       #include 
       
        using namespace std;char str[1000005];char pi[10005];int nex[10005];int m, n;void getNext(char *p, int *ne){    ne[0] = -1;    int i = -1, j = 0;    while (j < n) //注意循环的范围，之前错在 j
        
         > T;    while (T--)    {        scanf("%s", pi);        scanf("%s", str);        n = strlen(pi);        m = strlen(str);        getNext(pi, nex);        cout << kmpSearch() << endl;    }}