pku 3461 kmp(模板)

2020-10-18 05:06发布

对于这两次的比赛感到很无语, 不知道是不是很久没比赛了,以至于忘了比赛时的那个节奏,哎。。。

很早做出来一道题,然后一直都在研究一道题, 中间很想再换一道,但是想着 等把这个搞出来了再看下面的吧。。。。

以至于到最后还是没有搞出来,其他题也没有看,。

哎,找不到感觉了,  决定这两天不再学习新的算法, 把以前学过的算法看一下,先把这几场比赛给应付过去。。。

今天被这个kmp给难住了,尽管有一本算法导论,但是尽然抄错了。。

贴一个模板,以后自己再写kmp就全部按照这个写。。。。。

View Code
1 # include<stdio.h>
2 # include<string.h>
3  char P[10005],T[1000005];
4  int next[10005],n,m;
5 void Pnex()
6 {
7 int k,q;
8 next[1]=0;
9 k=0;
10 for(q=2;q<=n;q++)
11 {
12 while(k>0 && P[k+1]!=P[q])
13 {
14 k=next[k];
15 }
16 if(P[k+1]==P[q]) k++;
17 next[q]=k;
18 }
19 }
20 int main()
21 {
22 int i,t,q,num;
23 scanf("%d",&t);
24 getchar();
25 while(t--)
26 {
27 gets(P);
28 gets(T);
29 n=strlen(P);
30 m=strlen(T);
31 for(i=n-1;i>=0;i--)
32 P[i+1]=P[i];
33 for(i=m-1;i>=0;i--)
34 T[i+1]=T[i];
35 Pnex();
36 q=0;
37 num=0;
38 for(i=1;i<=m;i++)
39 {
40 while(q>0 && P[q+1]!=T[i])
41 {
42 q=next[q];
43 }
44 if(P[q+1]==T[i]) q++;
45 if(q==n)
46 {
47 num++;
48 q=next[q];
49 }
50 }
51 printf("%d\n",num);
52 }
53 return 0;
54 }
标签: