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
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
题目大意:
【题目描述】
判断是否能将字符串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