hdu 4763 && 2013 ACM/ICPC 长春网络赛解题报告

一个KMP的简单题

不过好久没用过这个东东了，今天写的时候花了很多时间；

只需要花点时间判断下所有的元素都相同的的情况就行了！

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<algorithm>
 4 #define maxn 1000006
 5 using namespace std;
 6 char s[maxn];
 7 int next[maxn];
 8 
 9 void getnext(char *t)
10 {
11     //    t为模式串
12     int i=0,j= -1,l = strlen(t);
13     next[0] = -1;
14     while(i < l)
15     {
16         if(j == -1 || t[i]==t[j])
17         {
18             ++i;
19             ++j;
20             next[i] = j;
21         }
22         else j = next[j];
23     }
24 }
25 
26 int main()
27 {
28     int t;
29     scanf("%d",&t);
30     while(t--)
31     {
32         memset(next,0,sizeof next);
33         scanf("%s",&s);
34         getnext(s);
35         int l=strlen(s);
36         bool flag=0,ff=1;
37         int i;
38         for(i=1; i<l; i++)
39             if((next[i]+1)!=next[i+1]) {ff=0;break;}
40         if(ff==1){printf("%d
",(next[l]+1)/3);continue;}
41 
42         for(int j=2; j<l; j++)
43         {
44             if(next[j]==next[l])
45             {
46                 printf("%d
",next[l]);
47                 flag=1;
48                 break;
49             }
50         }
51         if(!flag)
52         {
53             int a=max(i/2,next[l]/2);
54             printf("%d
",a);
55         }
56     }
57     return 0;
58 }

View Code