HDU5340 Three Palindromes

    xiaoxiao2021-04-16  27

    Three Palindromes

    Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)Total Submission(s): 1680    Accepted Submission(s): 596http://acm.hdu.edu.cn/showproblem.php?pid=5340

    Problem Description

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

     

    Input

    First line contains a single integer T20 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

    题目大意:

    【题目描述】 判断是否能将字符串S分成三段 非空回文串。 【输入说明】 第一行一个整数T,表示数据组数。 对于每一个组,仅包含一个由小写字母组成的串。 【输出说明】 对于每一组,单行输出"Yes" 或 "No“     对每组数据跑一边Manacher是为了求最大半径数组rad[] 由于题目要求分成三部分,所以需要两个断点,分成第一、二、三三个部分 预处理出一、三为回文串的情况,也就是记录下回文前缀和回文后缀的位置,方便直接调用 枚举上一步找到的两个断点,确定下目前需要讨论的第二区间,其中点对应的半径*2-1如果>=区间长度,则说明符合条件,break掉   #include<iostream>//把注释去掉,上面的加注释将是另一种表示方法 #include<cstdio> #include<cstring> using namespace std; int Case,rad[20010*3],q1[20010*3],q2[20010*3]; char s[20010],c[20010*3]; void manacher(){ int len=strlen(s+1); for(int i=len;i>=0;i--){ c[i*2]=s[i]; c[i*2+1]='#'; }c[0]='$'; int k=0; for(int i=1;i<=len*2;i++){ if(rad[k]+k>i)rad[i]=min(k+rad[k]-i,rad[2*k-i]); else rad[i]=1; while(c[i-rad[i]]==c[i+rad[i]])rad[i]++; if(i+rad[i]>k+rad[k])k=i; } } int main(){ scanf("%d",&Case); while(Case--){ int l=0,r=0; memset(rad,0,sizeof(rad)); memset(q1,0,sizeof(q1)); memset(q2,0,sizeof(q2)); scanf("%s",s+1); int n=strlen(s+1);n=n*2+1; manacher(); for(int i=1;i<=n;i++){ if(i==rad[i]&&i!=1)q1[++l]=i; if(n+1-i==rad[i]&&i!=n)q2[++r]=i; /*if(i==rad[i]&&i!=1)q1[++l]=rad[i]; if(n+1-i==rad[i]&&i!=n)q2[++r]=rad[i];*/ } bool flag=0;int t1,t2; for(int i=1;i<=l;i++){ if(flag==1)break; for(int j=1;j<=r;j++){ t1=q1[i]*2;t2=n-2*(n-q2[j])-1; /*t1=q1[i]*2;t2=n+1-q2[j]*2;*/ if(t1>t2)continue; if(t2-t1==1)continue; int mid=(t1+t2)>>1; if(rad[mid]*2-1>=t2-t1+1){flag=1;break;} } } if(flag==1){printf("Yes\n");} else printf("No\n"); } }
    转载请注明原文地址: https://ju.6miu.com/read-672119.html

    最新回复(0)