Three PalindromesTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 80Accepted Submission(s): 21
Problem Description
Can we divided a given string S into three nonempty palindromes?
Input
First line contains a single integer
which denotes the number of test cases.For each test case , there is an single line contains a string S which only consist of lowercase English letters.
Output
For each case, output the "Yes" or "No" in a single line.
Sample Input
2abcabaadada
Sample Output
YesNo
题意，是给出一个字符串，能否分成三个非空回文串。
我们可以发现 第一个和第三个串，一定是最大回文串的某个串,Manacher 求出最大回文串的长度，枚举第一个和最后一个，中间直接判断，中点的最大回文串是否包括了就可以了。复杂度为o(n * n).
具体manacher算法参见Manacher算法
#define N 110050#define M 100005#define maxn 205#define MOD 1000000000000000007int T,n,a,pri[N],ans,len,sn = 0,top[N],tail[N],pn,ln;bool dp[N][4];pii seg[N];bool Manacher(char str[],int len){char tstr[N+N];int p[N + N],l2 =0,mi;tstr[l2++] = '#';for(int i =0;i<len;i++){tstr[l2++] = str[i];tstr[l2++] = '#';}p[0] = 0;mi = 0;for(int i = 1;i<l2;i++){int mi2 = mi + mi – i;if(mi + p[mi] >= i) p[i] = min(mi2 – (mi – p[mi]),p[mi2]);else p[i] = 0;if(p[i] == 0 || mi2 – p[mi2] == mi – p[mi]){int maxx = p[i]+1;while(i- maxx >= 0 && i+maxx < l2 && tstr[i-maxx] == tstr[i+maxx]){maxx++;}p[i] = maxx – 1;}if(p[i] + i > p[mi] + mi) mi = i;}int ans = -1;sn = 0;pn = ln = 0;for(int i = 1;i < l2 – 1;i++){if(i – p[i] == 0) top[pn++] = i;if(i + p[i] == l2 – 1) tail[ln++] = i;}for(int i = 0;i < pn;i++){for(int j = ln – 1;j>=0;j–){int s1 = top[i] + p[top[i]] + 1,s2 = tail[j] – p[tail[j]] – 1;if(s1 > s2 )break;int mid = (s1 + s2)/2;if(p[mid] >= mid – s1) return true;}}return false;//printf("%d\n",ans);}char str[N];int main(){while(S(T)!=EOF){while(T–){SS(str);len = strlen(str);if(Manacher(str,len))printf("Yes\n");elseprintf("No\n");}}return 0;}
Source
Recommend
hujie|We have carefully selected several similar problems for you:53425341533953385337
版权声明：本文为博主原创文章，，未经博主允许不得转载。
最有效的资本是我们的信誉，它24小时不停为我们工作。
