题意
求一个字符串中本质不同的回文子串的个数。
$ 1leq |string| leq 100000$
思路
好像是回文自动机的裸题，但是可以用 ( ext{Manacher}) （马拉车）算法配合后缀数组（或配合哈希表）解决。
( ext{Manacher}) 算法非常短小精悍，它可以在线性时空内求出以每个点为中心拓展的最远距离，筛出与 (n) 同阶个数个回文串，这些回文串包含原串所有本质不同的回文串。
为了判掉奇偶串的问题，我们为字符串穿插一个特殊字符，如字符串 abccba，就变成了 #a#b#c#c#b#a#。
设每个点向两边拓展形成的最远距离（包含本身）为数组 (p) ，那么上述字符串对应的 (p) 数组如下：
| str | # | a | # | b | # | c | # | c | # | b | # | a | # |
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| p | 1 | 2 | 1 | 2 | 1 | 2 | 7 | 2 | 1 | 2 | 1 | 2 | 1 |
不难看出，(max{p}-1) 就是原串的最长回文串长度，同理每个字符向两边拓展的最远距离也可以得到。
算法流程也比较简短，首先维护两个变量，(mr( ext{max right})) 和 (pos( ext{mid position})) ，分别表示已经求出右端点最靠右的子串的右端点和中心位置。如果目前要求的 (i) 节点没有超过 (mr)，那么 (p[i]) 就可以是 (p[2*pos-i]) （对称点），但要对 (mr-i+1) 取 (min)，因为在 (mr) 右边的字符还不知道。如果 (i) 节点超过了 (mr) ，那就先直接取 (1) 。接下来就暴力继续匹配，因为一次成功匹配必然会带动右端点的推动，所以复杂度是 (O(n)) 的，代码如下：
void Manacher(char *str,int len)
{
int n=1;
mnc[1]='#';
FOR(i,1,len)mnc[++n]=str[i],mnc[++n]='#';
int mr=0,pos;
FOR(i,1,n)
{
if(i<=mr)p[i]=std::min(p[(pos<<1)-i],mr-i+1);
else p[i]=1;
while(i-p[i]>=1&&i+p[i]<=n&&mnc[i-p[i]]==mnc[i+p[i]])p[i]++;
if(chk_max(mr,i+p[i]-1))pos=i;
}
}
( ext{Manacher}) 算法进行 p[i]++ 时可以得到所有本质不同的回文串（不保证无重复）。
注意到一个与已经找过的串本质不同的回文串，一定能通过一次推动右端点得到，并且一次推动右端点最多增加一个回文串（如果以这个位置为右端点存在多个回文串，那么不是最长的串肯定在之前算过），这也同时证明了一个串内本质不同的回文子串是 (O(n)) 级别的。
那么可以利用 ( ext{Manacher}) 求出若干个回文串，这一定包含了所有本质不同的回文子串，我们只用对它进行去重即可，后缀数组可以很方便的实现它，对长度相同的串，按 (rk) 进行排序，比较 ( ext{lcp}) 是否为串长即可。
代码
#include<bits/stdc++.h>
#define FOR(i,x,y) for(int i=(x),i##END=(y);i<=i##END;++i)
#define DOR(i,x,y) for(int i=(x),i##END=(y);i>=i##END;--i)
template<typename T,typename _T>inline bool chk_min(T &x,const _T y){return y<x?x=y,1:0;}
template<typename T,typename _T>inline bool chk_max(T &x,const _T y){return x<y?x=y,1:0;}
typedef long long ll;
const int N=2e5+5;
struct SparseTable
{
int st[N][19],bin[(1<<18)+5];
void init(int *arr,int n)
{
bin[1]=0;FOR(i,2,1<<18)bin[i]=bin[i>>1]+1;
FOR(i,1,n)st[i][0]=arr[i];
FOR(j,1,18)FOR(i,1,n-(1<<j)+1)
st[i][j]=std::min(st[i][j-1],st[i+(1<<(j-1))][j-1]);
}
int query(int l,int r)
{
int k=bin[r-l+1];
return std::min(st[l][k],st[r-(1<<k)+1][k]);
}
}SH;
int sa[N],rk[N],H[N],tmp[3][N];
char str[N];
char mnc[N];int p[N];
int n;
struct node
{
int l,r;
bool operator <(const node &_)const
{
if(r-l+1!=_.r-_.l+1)return r-l+1<_.r-_.l+1;
else return rk[l]<rk[_.l];
}
}pld[N];int pc;
void get_SA(char *s,int n,int m)
{
int *x=tmp[0],*y=tmp[1],*c=tmp[2];
memset(tmp,0,sizeof(tmp));
x[n+1]=y[n+1]=0;
FOR(i,1,m)c[i]=0;
FOR(i,1,n)c[x[i]=s[i]]++;
FOR(i,2,m)c[i]+=c[i-1];
DOR(i,n,1)sa[c[x[i]]--]=i;
for(int k=1;k<=n;k<<=1)
{
int p=0;
FOR(i,n-k+1,n)y[++p]=i;
FOR(i,1,n)if(sa[i]>k)y[++p]=sa[i]-k;
FOR(i,1,m)c[i]=0;
FOR(i,1,n)c[x[y[i]]]++;
FOR(i,2,m)c[i]+=c[i-1];
DOR(i,n,1)sa[c[x[y[i]]]--]=y[i];
std::swap(x,y);
p=x[sa[1]]=1;
FOR(i,2,n)x[sa[i]]=y[sa[i]]==y[sa[i-1]]&&y[sa[i]+k]==y[sa[i-1]+k]?p:++p;
if(n==p)break;
m=p;
}
FOR(i,1,n)rk[sa[i]]=i;
int k=0;
FOR(i,1,n)
{
if(k)k--;
if(rk[i]==1)continue;
int j=sa[rk[i]-1];
while(i+k<=n&&j+k<=n&&s[i+k]==s[j+k])k++;
H[rk[i]]=k;
}
SH.init(H,n);
}
int get_lcp(int x,int y)
{
if(x==y)return n-x+1;
x=rk[x],y=rk[y];
if(x>y)std::swap(x,y);
return SH.query(x+1,y);
}
void Manacher(char *str,int len)
{
int n=1;
mnc[1]='#';
FOR(i,1,len)mnc[++n]=str[i],mnc[++n]='#';
pc=0;
int mr=0,pos;
FOR(i,1,n)
{
if(i<=mr)p[i]=std::min(p[(pos<<1)-i],mr-i+1);
else p[i]=1;
while(i-p[i]>=1&&i+p[i]<=n&&mnc[i-p[i]]==mnc[i+p[i]])
{
p[i]++;
if(mnc[i-p[i]+1]=='#')
pld[++pc]=(node){(i-p[i]+1+1)/2,(i+p[i]-1-1)/2};
}
if(chk_max(mr,i+p[i]-1))pos=i;
}
}
int main()
{
int T;
scanf("%d",&T);
FOR(Ti,1,T)
{
scanf("%s",str+1);
n=strlen(str+1);
get_SA(str,n,256);
Manacher(str,n);
std::sort(pld+1,pld+1+pc);
int ans=1;
FOR(i,2,pc)
{
if(pld[i].r-pld[i].l+1==pld[i-1].r-pld[i-1].l+1&&get_lcp(pld[i].l,pld[i-1].l)>=pld[i].r-pld[i].l+1)
continue;
else ans++;
}
printf("Case #%d: %d
",Ti,ans);
}
return 0;
}