题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5340
题意：给定一个字符串，问可不可以把它分成三个字符串
这个题的思路很简单，首先我们先跑一遍Manacher算法，在O(2*n)的复杂度下求出每一个点的以之为中心的回文串长度，然后我们再枚举第一个和第三个，满足第一个和第三个的条件就是回文串长度要延伸到两头。在枚举了两头的之后我们再看中间是否存在符合条件的。
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int maxn = 1000005;
char str[maxn];
char initstr[maxn];
int p[maxn],ls[maxn],rs[maxn];
int init()
{initstr[0] = '$';int num =1;int len = strlen(str);for(int i=0; i<len; i++){initstr[num++] = '#';initstr[num++] = str[i];}initstr[num++] = '#';initstr[num] = '\0';return num;
}
void manacher(int n)
{int id, Max = 0;for(int i=0; i<n; i++){if(Max > i) p[i] = min(p[2*id-i], Max-i);else p[i] = 1;while(initstr[i-p[i]] == initstr[i+p[i]]) p[i]++;if(Max < i+p[i]){Max = i+p[i];id = i;}}
}
int main()
{int T;scanf("%d",&T);while(T--){scanf("%s",str);int num = init();manacher(num);int ln = 0,rn = 0;for(int i=0; i<num; i++){if(p[i] == i && i!=1) ls[ln++] = p[i];if(p[i] == num-i && i!=num-1) rs[rn++] = p[i];}int ok = 0;for(int i=ln-1; i>=0; i--){for(int j=0; j<=rn-1; j++){int l = 2*ls[i];int r = num-2*rs[j];int mid = (l+r)/2;if(l > r || p[mid] == 1) continue;if(p[mid]*2-1 >= r-l+1){ok = 1;break;}}if(ok) break;}if(ok) printf("Yes\n");else printf("No\n");}
}