HDU5340 Three Palindromes
2024-09-05 04:38:43
Three Palindromes
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 1680 Accepted Submission(s):
596
http://acm.hdu.edu.cn/showproblem.php?pid=5340
Problem Description
Can we divided a given string S into three nonempty
palindromes?
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.
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[*],q1[*],q2[*];
char s[],c[*];
void manacher(){
int len=strlen(s+);
for(int i=len;i>=;i--){
c[i*]=s[i];
c[i*+]='#';
}c[]='$';
int k=;
for(int i=;i<=len*;i++){
if(rad[k]+k>i)rad[i]=min(k+rad[k]-i,rad[*k-i]);
else rad[i]=;
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=,r=;
memset(rad,,sizeof(rad));
memset(q1,,sizeof(q1));
memset(q2,,sizeof(q2));
scanf("%s",s+);
int n=strlen(s+);n=n*+;
manacher();
for(int i=;i<=n;i++){
if(i==rad[i]&&i!=)q1[++l]=i;
if(n+-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=;int t1,t2;
for(int i=;i<=l;i++){
if(flag==)break;
for(int j=;j<=r;j++){
t1=q1[i]*;t2=n-*(n-q2[j])-;
/*t1=q1[i]*2;t2=n+1-q2[j]*2;*/
if(t1>t2)continue;
if(t2-t1==)continue;
int mid=(t1+t2)>>;
if(rad[mid]*->=t2-t1+){flag=;break;}
}
}
if(flag==){printf("Yes\n");}
else printf("No\n");
}
}
最新文章
- easyui rowStyler属性
- 3.OGG函数
- nginx的优化
- [MongoDB] Insert, find -- 1
- C++中使用多线程
- Java基础知识强化60:经典查找之二分查找
- java 成员访问修饰符
- 将php分页类YII绑定框架,就需要改变风格的基础
- Android 开发环境 —— Eclipse 启动时报错:Error when loading the SDK
- Java_Date_01_判断两个时间相差的天数
- Redis实战 - 2.list、set和Sorted Set
- Goroutine通信与thread in java间的通信
- [转]ORACLE 11G 导出报错(EXP-00003)未找到段 (0,0) 的存储定义
- JS使用cookie实现只出现一次的广告代码效果
- spring security运行流程图(转)
- docker registry v2与harbor的搭建
- server下apache2.4.*虚拟主机配置Forbidden You don&#39;t have permission to access / on this server.
- 写给大忙人的spring cloud 1.x学习指南
- HDU 6155 Subsequence Count(矩阵乘法+线段树+基础DP)
- English Phrases with THE – Linking the TH Sound