The Number of Palindromes
Problem DescriptionNow, you are given a string S. We want to know how many distinct substring of S which is palindrome.InputThe first line of the input contains a single integer T(T<=20), which indicates number of test cases.
Each test case consists of a string S, whose length is less than 100000 and only contains lowercase letters.OutputFor every test case, you should output "Case #k:" first in a single line, where k indicates the case number and starts at 1. Then output the number of distinct substring of S which is palindrome.Sample Input3aaaaabababcdSample OutputCase #1: 4Case #2: 4Case #3: 4
【题意】
统计一个字符串内有多少个不同的回文串。
【分析】
这道题主要是去重。
一开始我打的去重还是很有问题，还是看别人的才打出来了。
把原串反向加入到原串后面，中间插入特殊字符。后缀数组求sa、height。
分奇偶，奇串和偶串肯定是不同种的。然后对于一个位置i，找到对应位置，用rmq求区间min。
去重：用cnt记录目前计算的回文长度与height的min值（所以这里计算的时候要按字符串大小顺序计算）。
如果有新增回文串，就加进去，并更新cnt。
主要是最后一步，要好好理解。
代码如下:
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
#define Maxl 200010
#define INF 0xfffffff int c[Maxl];
int n,cl,l; int mymin(int x,int y) {return x<y?x:y;}
int mymax(int x,int y) {return x>y?x:y;} char s[Maxl];
void init()
{
scanf("%s",s);
l=strlen(s);cl=;
for(int i=;i<l;i++) c[++cl]=s[i]-'a'+;
c[++cl]=;
for(int i=l-;i>=;i--) c[++cl]=s[i]-'a'+;
} int sa[Maxl],rk[Maxl],Rs[Maxl],y[Maxl],wr[Maxl];
void get_sa(int m)
{
memcpy(rk,c,sizeof(rk));
for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[rk[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[rk[i]]--]=i; int ln=,p=;//p表示目前有多少个不一样的rk
while(p<cl)
{
int k=;
for(int i=cl-ln+;i<=cl;i++) y[++k]=i;
for(int i=;i<=cl;i++) if(sa[i]>ln) y[++k]=sa[i]-ln;
for(int i=;i<=cl;i++)
wr[i]=rk[y[i]]; for(int i=;i<=m;i++) Rs[i]=;
for(int i=;i<=cl;i++) Rs[wr[i]]++;
for(int i=;i<=m;i++) Rs[i]+=Rs[i-];
for(int i=cl;i>=;i--) sa[Rs[wr[i]]--]=y[i]; for(int i=;i<=cl;i++) wr[i]=rk[i];
for(int i=cl+;i<=cl+ln;i++) wr[i]=;
p=,rk[sa[]]=;
for(int i=;i<=cl;i++)
{
if(wr[sa[i]]!=wr[sa[i-]]||wr[sa[i]+ln]!=wr[sa[i-]+ln]) p++;
rk[sa[i]]=p;
}
ln*=;m=p;
}
sa[]=rk[]=;
} int height[Maxl];
void get_he()
{
int k=;
for(int i=;i<=cl;i++) if(rk[i]!=)
{
int j=sa[rk[i]-];
if(k) k--;
while(c[i+k]==c[j+k]&&i+k<=cl&&j+k<=cl) k++;
height[rk[i]]=k;
}
height[]=;
} int d[Maxl][];
void rmq_init()
{
for(int i=;i<=cl;i++) d[i][]=height[i];
for(int j=;(<<j)<=cl;j++)
for(int i=;i+(<<j)-<=cl;i++)
d[i][j]=mymin(d[i][j-],d[i+(<<j-)][j-]);
} int rmq(int x,int y)
{
int t;
if(x>y) t=x,x=y,y=t;
x++;
int k=;
while((<<(k+))<=y-x+) k++;
return mymin(d[x][k],d[y-(<<k)+][k]);
} int ans;
void ffind()
{
int cnt=;ans=;
//奇
for(int i=;i<=cl-n;i++)
{
cnt=mymin(cnt,height[i]);
if(sa[i]<=l)
{
int j=rk[cl-sa[i]+];
int tem=rmq(i,j);
if(tem>cnt)
{
ans+=(tem-cnt);
cnt=tem;
}
}
}
//偶
cnt=;
for(int i=;i<=cl-n;i++)
{
cnt=mymin(cnt,height[i]);
if(sa[i]<=l)
{
int j=rk[cl-sa[i]+];
int tem=rmq(i,j);
if(tem>cnt)
{
ans+=tem-cnt;
cnt=tem;
}
}
}
} int main()
{
int T,kase=;
scanf("%d",&T);
while(T--)
{
init();
get_sa(+n);
get_he();
rmq_init();
ffind();
printf("Case #%d: %d\n",++kase,ans);
}
return ;
}
[HDU3948]
2016-07-19 09:46:16