回文串(palindromes)
【题目描述】
判断是否能将字符串S分成三段非空回文串。
【输入说明】
第一行一个整数T，表示数据组数。
对于每一个组，仅包含一个由小写字母组成的串。
【输出说明】
对于每一组，单行输出"Yes" 或 "No"。
【样例输入】
2
abc
abaadada
【样例输出】
Yes
No
【数据范围】
对于40%的数据，|S|<=100
对于60%的数据，|S|<=1000
对于100%的数据，T<=20，|S|<=20000
#include<iostream>
#include<cstdio>
#include<cstring>
#define maxn 20010
#define P 29
#define ll long long
using namespace std;
ll T,n,A[maxn],B[maxn],a[maxn],b[maxn],p[maxn],flag;
char s[maxn];
void Get()
{
p[]=;
for(int i=;i<=;i++)
p[i]=p[i-]*P;
}
void Hash1()
{
A[]=;
for(int i=;i<=n;i++)
A[i]=A[i-]*P+s[i];
}
void Hash2()
{
B[]=;
for(int i=;i<=n;i++)
B[i]=B[i-]*P+s[n-i+];
}
ll query2(ll l,ll r)
{
return B[r]-B[l-]*p[r-l+];
}
ll query1(ll l,ll r)
{
return A[r]-A[l-]*p[r-l+];
}
int main()
{
scanf("%d",&T);
Get();
while(T--)
{
scanf("%s",s+);
n=strlen(s+);
a[]=;b[]=;
Hash1();Hash2();flag=;
for(int i=;i<=n;i++)
{
ll x=query1(,i);
ll y=query2(n-i+,n);
if(x==y) a[++a[]]=i;
}
for(int i=n;i>=;i--)
{
ll x=query1(i,n);
ll y=query2(,n-i+);
if(x==y) b[++b[]]=i;
}
for(int i=;i<=a[];i++)
{
for(int j=;j<=b[];j++)
{
if(a[i]+>b[j]-) break;
ll x=query1(a[i]+,b[j]-);
ll y=query2(n-b[j]+,n-a[i]);
if(x==y)
{
flag=;break;
}
}
if(flag) break;
}
if(flag) printf("Yes\n");
else printf("NO\n");
} return ;
}
八十分做法~~~，已跪，求大神解救~~