【codevs2183】匹配字符串

KMP裸题

 1 #include<algorithm>
 2 #include<iostream>
 3 #include<cstdlib>
 4 #include<cstring>
 5 #include<cstdio>
 6 #include<cmath>
 7 using namespace std;
 8 
 9 #define N 200010
10 
11 char a[N],b[N];
12 int p[N],cnt[N];
13 
14 int l1,l2,t;
15 int x;
16 
17 int main()
18 {
19     scanf("%d%d%d",&l1,&l2,&t);    
20     scanf("%s%s",a+1,b+1);
21     for (int i=2,j=0;i<=l2;i++)
22     {
23         while (j>0 && b[i]!=b[j+1])
24             j=p[j];
25         if (b[i]==b[j+1])
26             j++;
27         p[i]=j;
28     }
29     for (int i=1,j=0;i<=l1;i++)
30     {
31         while (j>0 && a[i]!=b[j+1])
32             j=p[j];
33         if (a[i]==b[j+1])
34             ++j;
35         ++cnt[j];
36     }
37     for (int i=l1;i>0;i--)
38         cnt[p[i]]+=cnt[i];
39     while (t--)
40     {
41         scanf("%d",&x);
42         printf("%d
",cnt[x]-cnt[x+1]);
43     }
44     return 0;
45 }