HDU2203

View Code

 1 #include<stdio.h>
 2 #include<string.h>
 3 #define N 100005
 4 int next[N];
 5 int flag,len2,len1;
 6 char str1[2*N],str2[N];
 7 
 8 void getnext()
 9 {
10     int i,j,k;
11     memset(next,0,sizeof(next));
12     next[0]=-1;
13     j=0;
14     k=-1;
15     while(j<len2)
16     {
17         if(k==-1||str2[j]==str2[k])
18         {
19             k++;
20             j++;
21             next[j]=k;
22         }
23         else
24             k=next[k];
25     }
26     return ;
27 }
28 
29 void kmp()
30 {
31     int i,j,k;
32     getnext();
33     j=k=0;
34     while(j<len1&&k<len2)
35     {
36         if(k==-1||str1[j]==str2[k])
37         {
38             j++;
39             k++;
40         }
41         else
42             k=next[k];
43     }
44     if(k==len2)
45     {
46         flag=1;
47     }
48     return ;
49 }
50 
51 int main()
52 {
53     int i,j,k;
54     while(scanf("%s%s",str1,str2)!=EOF)
55     {
56         flag=-1;
57         len1=strlen(str1);
58         len2=strlen(str2);
59         if(len1<len2)
60         {
61             printf("no\n");
62             continue;
63         }
64         for(i=0;i<len1;i++)
65             str1[i+len1]=str1[i];
66         str1[len1*2]='\0';
67         len1=len1*2;
68         kmp();
69         if(flag==1) printf("yes\n");
70         else printf("no\n");
71     }
72     return 0;
73 }

关键在于循环。

可以把str1字符串再接在str1字符串的后面，这样所有的循环都考虑到了。

不过这样要在kmp之前，判断len1，len2.

keep moving...