Three Palindromes

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1244    Accepted Submission(s): 415

Problem Description

Can we divided a given string S into three nonempty palindromes?

 

 

Input

First line contains a single integer 

T≤20 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.1≤|s|≤20000

 

 

Output

For each case, output the "Yes" or "No" in a single line.

 

 

Sample Input

2 abc abaadada

 

 

Sample Output

Yes No

 

 

 

题目大意：问是否可以找出三段回文串。

 

题解：

没有进行暴力压位，时间接近超时。但是很侥幸过了。

 

#include
      
       using namespace std;#define min(a,b) ((a)<(b)?(a):(b))const int maxn=20200;int pre[maxn*2],suf[maxn*2];int p[maxn*2];char str[maxn],trans[maxn*2];int Transform(){  //  memset(p,0,sizeof(p));    memset(pre,0,sizeof(pre));    memset(suf,0,sizeof(suf));    int len=strlen(str);    trans[0]='$';    for(int i=1;i<=2*len;i+=2){        trans[i]='#';        trans[i+1]=str[i/2];    }    trans[2*len+1]='#';    trans[2*len+2]='@';    return 2*len+1;}int manacher(){    int len=Transform();    int mx=0,pos=0;    for(int i=1;i<=len;i++){        if(i