题目链接：
3948 The Number of Palindromes
思路：
我们使用后缀数组+RMQ可以实现查找回文的功能，这题的重点的去重过程；
为了方便去重，我们不按字符串的下标来遍历，而按以及排好的rk[]的顺序去遍历；
维护一个变量cnt记录上次的回文串长度和此次高度数组两者的最小值，如果此次RMQ查询结果大于cnt，说明有新的回文串，否则就是重复的。
代码：
#include<iostream>
#include<string>
#include<cstring>
#include<algorithm>
using namespace std;
const int maxn=2e5+5;
string s,a,b;
int n,sa[maxn],cnt[maxn],t1[maxn],t2[maxn],rk[maxn],lcp[maxn];
void cal_sa(){
int m=127; n=s.length();
int i,*x=t1,*y=t2;
for(int i=0;i<m;i++) cnt[i]=0;
for(int i=0;i<n;i++) ++cnt[x[i]=s[i]];
for(int i=1;i<m;++i) cnt[i]+=cnt[i-1];
for(int i=n-1;i>=0;--i) sa[--cnt[x[i]]]=i;
for(int k=1;k<=n;k<<=1){
int p=0;
for(i=n-k;i<n;++i) y[p++]=i;
for(i=0;i<n;++i) if(sa[i]>=k) y[p++]=sa[i]-k;
for(i=0;i<m;++i) cnt[i]=0;
for(i=0;i<n;++i) ++cnt[x[y[i]]];
for(i=1;i<m;++i) cnt[i]+=cnt[i-1];
for(i=n-1;i>=0;--i) sa[--cnt[x[y[i]]]]=y[i];
swap(x,y);
p=1; x[sa[0]]=0;
for(i=1;i<n;++i) x[sa[i]]=y[sa[i-1]]==y[sa[i]]&&y[sa[i-1]+k]==y[sa[i]+k]?p-1:p++;
if(p>=n) break; m=p;
}
}
void cal_lcp(){
for(int i=0;i<n;i++) rk[sa[i]]=i;
int h=0; lcp[0]=0;
for(int i=0;i<n;i++){
int j=sa[rk[i]-1];
if(h)--h;
while(j+h<n&&i+h<n&&s[j+h]==s[i+h])++h;
lcp[rk[i]]=h;
}
sa[n]=lcp[n]=rk[n]=0;
}
int dat[maxn][20],mm[maxn];
void initRMQ(int n,int b[]){
mm[0]=-1;
for(int i=1;i<=n;i++){
mm[i]=((i&(i-1))==0)?mm[i-1]+1:mm[i-1];
dat[i][0]=b[i];
}
for(int j=1;j<=mm[n];j++)
for(int i=1;i+(1<<j)-1<=n;i++)
dat[i][j]=min(dat[i][j-1],dat[i+(1<<(j-1))][j-1]);
}
int rmq(int x,int y){
if(x>y) swap(x,y); x++;
int k=mm[y-x+1];
return min(dat[x][k],dat[y-(1<<k)+1][k]);
}
void solve(){
b=a; reverse(b.begin(),b.end()); s=a+'$'+b;
cal_sa(); cal_lcp();
initRMQ(n,lcp);
int cnt=0,ans=0,pos=a.length();
for(int i=1;i<n;i++){
cnt=min(cnt,lcp[i]);
if(sa[i]<pos){
int j=rk[n-sa[i]-1];
int t=rmq(i,j);
if(t>cnt) ans+=(t-cnt),cnt=t;
}
}
cnt=0;
for(int i=1;i<n;i++){
cnt=min(cnt,lcp[i]);
if(sa[i]<pos){
int j=rk[n-sa[i]];
int t=rmq(i,j);
if(t>cnt) ans+=(t-cnt),cnt=t;
}
}
cout<<ans<<'
';
}
int main(){
// freopen("Sakura.txt","r",stdin);
ios::sync_with_stdio(false);
cin.tie(0);
int kase; cin>>kase;
for(int i=1;i<=kase;i++){
cin>>a; cout<<"Case #"<<i<<": ";
solve();
}
return 0;
}