【codevs】 1404 字符串匹配(KMP)

矫情吗；* 2022-09-30 03:41 176阅读 0赞

1404 字符串匹配  
时间限制: 1 s  
空间限制: 128000 KB  
题目等级 : 大师 Master  
链接：[点这里][Link 1]  
题解  
题目描述 Description  
给你两个串A，B，可以得到从A的任意位开始的子串和B匹配的长度。  
给定K个询问，对于每个询问给定一个x，求出匹配长度恰为x的位置有多少个。  
N，M，K<=200000

输入描述 Input Description  
第一行三个数 N，M，K，表示A的长度、B的长度和询问数。  
第二行为串A。  
第三行为串B。  
接下来K行，每行1个数X。

输出描述 Output Description  
对于每个询问输出一个数。

样例输入 Sample Input  
6 2 2  
aabcde  
ab  
0  
2

样例输出 Sample Output  
4  
1

#include <iostream>
    #include <cstdio>
    #include <cstring>
    #include <algorithm>
    
    using namespace std;
    
    const int N = 200010;
    
    int num[N];
    
    void get_next(char *t,int *next)
    {
       int i=0;//Prefix 前缀
       int j=1;//Postfix 后缀
       next[0] = 0;//自定义的，0和1都从0开始匹配
       next[1] = 0;
       while(t[j] != '\0')
       {
           if(t[i] == t[j])//若前后字符匹配，则向前推进
           {
               i++;
               j++;
               next[j] = i;
           }
           else
           {
               i = next[i];///前后字符不匹配，则回溯。注意，此时是i和j不匹配，因此，根据next数组定义，要回溯到next[i]的值
           }
           if(0 == i)//当回溯到首字符时，单独进行处理
           {
               if(t[i] == t[j])
               {
                   next[++j] = ++i;
               }
               else next[++j] = i;
           }
       }
    }
    
    void KMP(int *next,char *ch1,char *ch,int m,int n)
    {
        get_next(ch1,next);
    int j = 0;
    for(int i = 0; i < n; ++i)
    {
    while(j && ch[i] != ch1[j]) j = next[j];
    if(ch1[j] == ch[i]) j++;
    num[j]++;
    /* KMP中计算的num[]是统计以i为尾的匹配长度的数量，会将匹配失败的位置统计到当前匹配长度中，而不是统计到真的更小的匹配中，但总数依旧是不变的，且多统计的长度始终>=少统计的长度，于是我们倒序进行这个操作：num[next[j]]+=num[j]（next[]为失配指针） 因为匹配的时候，总是让j=next[j]，所以所有匹配到的>next[j]的位置，都会加入num[next[j]]的统计，此时所有可能的匹配长度>=L的位置都已经统计入num[L]中 然后那些漏掉的就补回来了，多算的没得补（也就是刚才的统计错误被修正了） 于是长度为x的答案就是num[x]-num[x+1]*/
    }
    }
    
    int main()
    {
    char ch[N], ch1[N];
    int n, m, k;
    int next[N];
    cin>>n>>m>>k;
    cin>>ch>>ch1;
    int x;
    KMP(next,ch1,ch,m,n);
        for(int i = m; i > 0; i--)
            num[next[i]] += num[i];
        for(int i = 0; i <= m; i++)
            num[i] -= num[i + 1];
    for(int i = 1; i <= k; ++i)
    {
    cin>>x;
    cout << num[x] << endl;
    }
    return 0;
    }

[Link 1]: http://codevs.cn/problem/1404/