2017.10.6 国庆清北 D6T3 字符串

题目描述

如果把一个字符串从头到尾翻转后和原字符串相等，我们称之为回文串，比如“aabaa”、“())(”、“2017102”。

如果一个字符串存在两个出现过的字母出现的次数相等，我们称之为好

的字符串。

现在给一个由小写字母组成的字符串，问在这个字符串的所有连续的串

中，好的回文串有多少个。(两个相同的回文串出现在不同位置算多次)。

输入输出格式

输入格式：

一行一个小写字母组成的字符串。

输出格式：

一行一个整数，表示答案。

输入输出样例

输入样例#1：

abcbaabcba

输出样例#1：

6
【样例解释】
abcba s[1..5] a,b 出现次数相等
baab s[4..7] a,b 出现次数相等
cbaabc s[3..8] a,b 出现次数相等
bcbaabcb s[2..9] a,c 出现次数相等
abcbaabcba s[1..10] a,b 出现次数相等
abcba s[6..10] a,b 出现次数相等

说明

len 表示字符串长度。

对于30% 的数据, len <=10^2。

对于60% 的数据, len <= 10^3。

对于100% 的数据，1 <= len <= 10^4。

  1 /*
  2 我们发现回文串是可以二分的
  3 比如：bbbabcbaabcba 我们以第1个c为中心，发现回文半径是3，大于3一定不是回文串。当回文串长度为偶数的时候，我们需要特殊处理一下。
  4 现在有一个结论：本质不同的回文串个数只有O(N)个
  5 本质不同：字符串本身是不同的。
  6 每一次处理完回文串，我们要把他的hash值记录下来。
  7 */
  8 
  9 #include<cstdio>
 10 #include<cstring>
 11 #include<algorithm>
 12 #include<map>
 13 using namespace std;
 14 
 15 typedef unsigned long long ULL;
 16 typedef long long LL;
 17 
 18 char s[10005];
 19 ULL h[10005],rh[10005],pw[10005];
 20 int L;
 21 
 22 ULL hs(int l,int r)
 23 {
 24     return h[r]-h[l-1]*pw[r-l+1];
 25 }
 26 ULL rhs(int l,int r)
 27 {
 28     return rh[l]-rh[r+1]*pw[r-l+1];
 29 }
 30 struct N
 31 {
 32     int a[26];
 33     bool ok(){
 34         int b[26];
 35         for(int i=0;i<26;i++) b[i]=a[i];
 36         sort(b,b+26);
 37         for(int i=0;i<25;i++)
 38         {
 39             if(b[i]>0&& b[i] == b[i+1]) return true;
 40         }
 41         return false;
 42     }
 43     void clear()
 44     {
 45         memset(a,0,sizeof a);
 46     }
 47 };
 48 LL ans=0;
 49 map<ULL,LL> num;
 50 map<ULL,N> A;
 51 void solve_odd()    //奇数 
 52 {
 53     for(int i=1;i<=L;i++)
 54     {
 55         int l=1,r=min(i,L-i+1)+1;
 56         while(r-l>1)
 57         {
 58             int mid=(l+r)/2;
 59             if(hs(i-mid+1,i+mid-1)==rhs(i-mid+1,i+mid-1)) l=mid;
 60             else r=mid;
 61         }
 62         int p=l;
 63         int tmp=p;
 64         while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp-1))==num.end()) tmp--;
 65         LL sum=0;
 66         N st;
 67         st.clear();
 68         if(tmp>=1)
 69         {
 70             sum=num[hs(i-tmp+1,i+tmp-1)];
 71             st=A[hs(i-tmp+1,i+tmp-1)];
 72         }
 73         while(tmp<p)
 74         {
 75             st.a[s[i+tmp]-'a']+=(tmp==0?1:2);
 76             if(st.ok()) sum++;
 77             num[hs(i-tmp,i+tmp)]=sum;
 78             A[hs(i-tmp,i+tmp)]=st;
 79             tmp++;
 80         }
 81         ans+=sum;
 82     }
 83 }
 84 void solve_even()    //偶数 
 85 {
 86     A.clear();
 87     num.clear();
 88     for(int i=1;i<L;i++)
 89     {
 90         int l=1,r=min(i,L-i)+1;
 91         while(r-l>1)
 92         {
 93             int mid=(l+r)/2;
 94             if(hs(i-mid+1,i+mid)== rhs(i-mid+1,i+mid)) l=mid;
 95             else r=mid;
 96         }
 97         int p=l;
 98         int tmp=p;
 99         while(tmp>=1&&num.find(hs(i-tmp+1,i+tmp))==num.end()) tmp--;
100         LL sum = 0;
101         N st;
102         st.clear();
103         if(tmp>=1)
104         {
105             sum=num[hs(i-tmp+1,i+tmp)];
106             st=A[hs(i-tmp+1,i+tmp)];
107         }
108         while(tmp<p)
109         {
110             st.a[s[i+tmp+1]-'a']+=2;
111             if(st.ok()) sum++;
112             num[hs(i-tmp,i+tmp+1)]=sum;
113             A[hs(i-tmp,i+tmp+1)]=st;
114             tmp++;
115         }
116         ans+=sum;
117     }
118 }
119 
120 int main()
121 {
122     scanf("%s",s+1);
123     L=strlen(s+1);
124     s[0]='#';
125     pw[0]=1;
126     for(int i=1;i<=L;i++) pw[i]=pw[i-1]*13131;        ///hash值 
127     for(int i=1;i<=L;i++) h[i]=h[i-1]*13131+s[i];
128     for(int i=L;i>=1;i--) rh[i]=rh[i+1]*13131+s[i];
129     solve_odd();
130     solve_even();
131     printf("%lld
",ans);
132     fclose(stdout);
133     return 0;
134 }

View Code