UVA12467Secret Word（KMP）

View Code
 1 #include<stdio.h>
 2 #include<string.h>
 3 char c1[1000011],c2[1000011];
 4 int next[1000011];
 5 int kmp()
 6 {
 7     int k = strlen(c1),i,j,y = -1;
 8     memset(next,0,sizeof(next));
 9     next[0] = -1;
10     for(i = 1; i < k ;i ++)
11     {
12         while(y>-1&&c1[i]!=c1[y+1])
13             y = next[y];
14         if(c1[y+1]==c1[i])
15             y++;
16         next[i] = y;
17     }
18     int max = -1;
19     y = -1;
20     for(i = 0 ; i < k ; i++)
21     {
22         while(y>-1&&c2[i]!=c1[y+1])
23         y = next[y];
24         if(c1[y+1]==c2[i])
25         {
26             y++;
27             if(max<y)
28             max = y;
29         }
30     }
31     return max;
32 }
33 int main()
34 {
35     int t,n,m,i,j,k;
36     scanf("%d%*c", &t);
37     while(t--)
38     {
39         gets(c1);
40         k = strlen(c1);
41         for(i =0 ;i <= k-1 ;i++)
42         {
43             c2[i] = c1[k-i-1];
44         }
45         n = kmp();
46         for(i = n ; i >= 0 ; i--)
47             printf("%c", c1[i]);
48         puts("");
49     }
50     return 0;
51 }