Description
順序和逆序讀起來完全一樣的串叫做回文串。比如
acbca
是回文串，而
abc
不是（
abc
的順序為
“abc”
，逆序為
“cba”
，不相同）。
輸入長度為
n
的串
S
，求
S
的最長雙回文子串
T,
即可将
T
分為兩部分
X
，
Y
，（
|X|,|Y|≥1
）且
X
和
Y
都是回文串。
Input
一行由小寫英文字母組成的字元串S。
Output
一行一個整數，表示最長雙回文子串的長度。
Sample Input
baacaabbacabb Sample Output
12
Hint
樣例說明
從第二個字元開始的字元串aacaabbacabb可分為aacaa與bbacabb兩部分，且兩者都是回文串。
對于100%的資料，2≤|S|≤10^5
2015.4.25新加資料一組
#pragma comment(linker, "/STACK:102400000,102400000")
#include<map>
#include<set>
#include<cmath>
#include<queue>
#include<stack>
#include<bitset>
#include<cstdio>
#include<string>
#include<cstring>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int a[maxn];
char s[maxn];
struct PalindromicTree
{
const static int maxn = 1e5 + 10;
const static int size = 26;
int next[maxn][size], sz, tot;
int fail[maxn], len[maxn], last;
char s[maxn];
void clear()
{
len[1] = -1; len[2] = 0;
fail[1] = fail[2] = 1;
last = (sz = 3) - 1; tot = 0;
memset(next[1], 0, sizeof(next[1]));
memset(next[2], 0, sizeof(next[2]));
}
int Node(int length)
{
memset(next[sz], 0, sizeof(next[sz]));
len[sz] = length; return sz;
}
int getfail(int x)
{
while (s[tot] != s[tot - len[x] - 1]) x = fail[x];
return x;
}
int add(char pos)
{
int x = (s[++tot] = pos) - 'a', y = getfail(last);
if (next[y][x]) { last = next[y][x]; }
else {
last = next[y][x] = Node(len[y] + 2);
fail[sz] = len[sz] == 1 ? 2 : next[getfail(fail[y])][x];
++sz;
}
return len[last];
}
}solve;
int main()
{
while (scanf("%s", s) != EOF)
{
int len = strlen(s), ans = a[0] = 0;
solve.clear();
for (int i = 0; s[i]; i++) a[i + 1] = solve.add(s[i]);
solve.clear();
for (int i = len; i; i--)
{
ans = max(ans, solve.add(s[i - 1]) + a[i - 1]);
}
printf("%d\n", ans);
}
return 0;
}