[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的位数；

然后，解决询问。

代码实现

 1 #include<cstdio>
 2 const int maxn=3e5;
 3 int n,m,k,a;
 4 char ch[maxn],cn[maxn];
 5 int next[maxn],ans[maxn];
 6 int main(){
 7     scanf("%d%d%d",&n,&m,&k);
 8     scanf("%s%s",ch+1,cn+1);
 9     for(int i=2,j=0;i<=m;i++){
10         while(j&&cn[j+1]!=cn[i]) j=next[j];
11         if(cn[j+1]==cn[i]) ++j;
12         next[i]=j;
13     }
14     for(int i=1,j=0;i<=n;i++){
15         while(j&&cn[j+1]!=ch[i]) j=next[j];
16         if(cn[j+1]==ch[i]) ++j;
17         ans[j]++;
18     }
19     for(int i=m;i>0;i--) ans[next[i]]+=ans[i];
20     for(int i=0;i<m;i++) ans[i]-=ans[i+1];
21     while(k--){
22         scanf("%d",&a);
23         printf("%d
",ans[a]);
24     }
25     return 0;
26 }

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