[codeVS1404] 字符串匹配

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 大师 Master

题目描述 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

数据范围及提示
Data Size & Hint

各个测试点1s

思路

KMP；

自己乱搞才得了10分，然后羞耻的看了题解；

先求B串next数组；

然后匹配，记录ans；

然后，这个ans是残缺的，需要倒序补充，ans[next[i]]+=ans[i]；

这样得到的ans[i]就会是匹配长度大于等于i的位数；

然后，解决询问。

代码实现

 #include<cstdio>

 const int maxn=3e5;

 int n,m,k,a;

 char ch[maxn],cn[maxn];

 int next[maxn],ans[maxn];

 int main(){

     scanf("%d%d%d",&n,&m,&k);

     scanf("%s%s",ch+,cn+);

     for(int i=,j=;i<=m;i++){

         while(j&&cn[j+]!=cn[i]) j=next[j];

         if(cn[j+]==cn[i]) ++j;

         next[i]=j;

     }

     for(int i=,j=;i<=n;i++){

         while(j&&cn[j+]!=ch[i]) j=next[j];

         if(cn[j+]==ch[i]) ++j;

         ans[j]++;

     }

     for(int i=m;i>;i--) ans[next[i]]+=ans[i];

     for(int i=;i<m;i++) ans[i]-=ans[i+];

     while(k--){

         scanf("%d",&a);

         printf("%d\n",ans[a]);

     }

     return ;

 }

KMP的题都好玄学，还是我变傻了。。。

巴特西

[codeVS1404] 字符串匹配

思路

代码实现

最新文章

热门文章