Three PalindromesTime Limit: 2000/1000 MS (Java/Others)Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 871Accepted Submission(s): 262
Problem Description
Can we divided a given string S into three nonempty palindromes?
Input
First line contains a single integerwhich 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
Source
Recommend
hujie|We have carefully selected several similar problems for you:53425341533953385337
#include <bits/stdc++.h>using namespace std;int t;int p[220100];char s[220100], c[221000];int len;void palindrome(){len = strlen(s);c[0] = '$';for (int i = 0; i<len; i++)c[i * 2 + 1] = '#', c[i * 2 + 2] = s[i];c[len * 2 + 1] = '#';len = len * 2 + 2;c[len] = '\0';int mx = 0, id = 0;for (int i = 1; i<len; i++){if (mx>i) p[i] = min(p[id * 2 – i], mx – i);else p[i] = 1;while (c[i + p[i]] == c[i – p[i]]) p[i]++;if (i + p[i]>mx) mx = i + p[i], id = i;}}int solve(){for(int i=2; i<len; i++){if(i – p[i] != 0) continue;for(int j=i+p[i]; j<len; j++){if(j-p[j]+1 <= i+p[i]){int x = j – ( i + p[i] );int last = (len + j + x) >> 1;if(last <= len – 2 && last + p[last] == len)return 1;}}}return 0;}int main(){scanf("%d", &t);while (t–){scanf("%s", s);palindrome();if (solve()) printf("Yes\n");else printf("No\n");}return 0;}
版权声明：本文为博主原创文章，，未经博主允许不得转载。
生气是拿别人做错的事来惩罚自己
