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<bits/stdc++.h>

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<mx){

            p[i]=min(p[2*pos-i],mx-i);

        }else{

            p[i]=1;

        }

        for(;trans[i+p[i]]==trans[i-p[i]];p[i]++);

        if(mx<i+p[i]){

            mx=i+p[i];

            pos=i;

        }

    }

    return len;

}

int main(){

    int t;

    scanf("%d",&t);

    while(t--){

        scanf("%s",str);

        int lens=strlen(str);

        if(lens<3){

            printf("No\n");continue;

        }else if(lens==3){

            printf("Yes\n");continue;

        }else{

            int len= manacher();

            for(int i=2;i<len;i++){

                if(p[i]==i){

                    pre[i+p[i]-1]=1;

                }

                if(p[i]==len-i+1){

                    suf[i-p[i]+1]=1;

                }

            }

            int flag=0;

            for(int i=2;i<len&&(!flag);i++){

                for(int j=1;j<p[i]&&(!flag);j++){

                    if(pre[i-j]&suf[i+j]){

                        flag=1;

                        printf("Yes\n");

                    }

                }

            }

            if(!flag){

                printf("No\n");

            }

        }

    }

    return 0;

}

巴特西

HDU 5340——Three Palindromes——————【manacher处理回文串】

Three Palindromes

最新文章

热门文章