HDU 3068 最长回文

最长回文

Time Limit: 2000ms

Memory Limit: 32768KB

This problem will be judged on HDU. Original ID: 3068
64-bit integer IO format: %I64d Java class name: Main

给出一个只由小写英文字符a,b,c...y,z组成的字符串S,求S中最长回文串的长度.
回文就是正反读都是一样的字符串,如aba, abba等

Input

输入有多组case,不超过120组,每组输入为一行小写英文字符a,b,c...y,z组成的字符串S
两组case之间由空行隔开(该空行不用处理)
字符串长度len <= 110000

Output

每一行一个整数x,对应一组case,表示该组case的字符串中所包含的最长回文长度.

Sample Input

aaaa

abab

Sample Output

4
3

Source

2009 Multi-University Training Contest 16 - Host by NIT

解题：Palindromic Tree

 1 #include <bits/stdc++.h>
 2 using namespace std;
 3 const int maxn = 200010;
 4 struct PalindromicTree{
 5     int son[maxn][26],fail[maxn],len[maxn],s[maxn];
 6     int tot,last,n,maxlen;
 7     int newnode(int slen = 0){
 8         len[tot] = slen;
 9         memset(son[tot],0,sizeof son[tot]);
10         return tot++;
11     }
12     void init(){
13         maxlen = tot = last = n = 0;
14         newnode(0);
15         newnode(-1);
16         fail[0] = fail[1] = 1;
17         s[n] = -1;
18     }
19     int getFail(int x){
20         while(s[n - len[x] -1] != s[n]) x = fail[x];
21         return x;
22     }
23     void extend(int c){
24         s[++n] = c;
25         int cur = getFail(last);
26         if(!son[cur][c]){
27             int x = newnode(len[cur] + 2);
28             fail[x] = son[getFail(fail[cur])][c];
29             son[cur][c] = x;
30             maxlen = max(maxlen,len[x]);
31         }
32         last = son[cur][c];
33     }
34 }pt;
35 char str[maxn];
36 int main(){
37     while(~scanf("%s",str)){
38         pt.init();
39         for(int i = 0; str[i]; ++i)
40             pt.extend(str[i] - 'a');
41         printf("%d
",pt.maxlen);
42     }
43     return 0;
44 }

View Code