济南学习 Day5 T3 晚

回文串(palindromes)

【题目描述】

判断是否能将字符串S分成三段非空回文串。

【输入说明】

第一行一个整数T，表示数据组数。

对于每一个组，仅包含一个由小写字母组成的串。

【输出说明】

对于每一组，单行输出"Yes" 或 "No"。

【样例输入】

abc

abaadada

【样例输出】

Yes

【数据范围】

对于40%的数据，|S|<=100

对于60%的数据，|S|<=1000

对于100%的数据，T<=20，|S|<=20000

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #define maxn 20010
 5 #define P 29
 6 #define ll long long 
 7 using namespace std;
 8 ll T,n,A[maxn],B[maxn],a[maxn],b[maxn],p[maxn],flag;
 9 char s[maxn];
10 void Get()
11 {
12     p[0]=1;
13     for(int i=1;i<=20000;i++)
14       p[i]=p[i-1]*P;
15 }
16 void Hash1()
17 {
18     A[0]=0;
19     for(int i=1;i<=n;i++)
20       A[i]=A[i-1]*P+s[i];
21 }
22 void Hash2()
23 {
24     B[0]=0;
25     for(int i=1;i<=n;i++)
26       B[i]=B[i-1]*P+s[n-i+1];
27 }
28 ll query2(ll l,ll r)
29 {
30     return B[r]-B[l-1]*p[r-l+1];
31 }
32 ll query1(ll l,ll r)
33 {
34     return A[r]-A[l-1]*p[r-l+1];
35 }
36 int main()
37 {
38     scanf("%d",&T);
39     Get();
40     while(T--)
41     {
42         scanf("%s",s+1);
43         n=strlen(s+1);
44         a[0]=0;b[0]=0;
45         Hash1();Hash2();flag=0;
46         for(int i=1;i<=n;i++)
47         {
48             ll x=query1(1,i);
49             ll y=query2(n-i+1,n);
50             if(x==y) a[++a[0]]=i;
51         }
52         for(int i=n;i>=1;i--)
53         {
54             ll x=query1(i,n);
55             ll y=query2(1,n-i+1);
56             if(x==y) b[++b[0]]=i;
57         }
58         for(int i=1;i<=a[0];i++)
59         {
60             for(int j=1;j<=b[0];j++)
61             {
62                 if(a[i]+1>b[j]-1) break;
63                 ll x=query1(a[i]+1,b[j]-1);
64                 ll y=query2(n-b[j]+2,n-a[i]);
65                 if(x==y)
66                 {
67                     flag=1;break;
68                 }
69             }
70             if(flag) break;
71         }    
72         if(flag) printf("Yes
");
73         else printf("NO
");
74     }
75     
76     
77     return 0;
78 }

八十分做法~~~，已跪，求大神解救~~