HDU 3068 最长回文

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<string.h>
 4 using namespace std;
 5 const int Nmax=110005;
 6 char s[Nmax];
 7 
 8 struct Manacher
 9 {
10 
11     int maxlen;
12     int id;
13     char str[Nmax*2+10];
14     int p[Nmax*2+10];
15     int str_len;
16     void init(char *s)
17     {
18         str[0]=‘$‘;
19         str[1]=‘#‘;
20         int n=strlen(s);
21         for(int i=0;i<n;i++)
22         {
23             str[i*2+2]=s[i];
24             str[i*2+3]=‘#‘;
25         }
26         str_len=n*2+2;
27         str[str_len]=‘@‘;
28         
29         id=0;
30         maxlen=0;
31     }
32     int get()
33     {
34         for(int i=2;i<str_len-1;i++)
35         {
36             if(p[id]+id>i)            
37                 p[i]=min( p[id]+id-i , p[id*2-i] );
38             else
39                 p[i]=1;
40             while( str[ i+p[i] ] == str[ i-p[i] ])
41                 p[i]++;
42             if(p[i]+i>p[id]+id)
43                 id=i;
44             if(p[i]>maxlen)
45                 maxlen=p[i];
46         }
47         return maxlen-1;
48     }
49 
50      
51 }manacher;
52 
53 int main()
54 {
55     while(scanf("%s",s)!=EOF)
56     {
57         manacher.init(s);
58         printf("%d\n",manacher.get());
59     }
60     return 0;
61 }