题意

求一个字符串中本质不同的回文子串的个数。

$ 1\leq |string| \leq 100000$

思路

好像是回文自动机的裸题，但是可以用 \(\text{Manacher}\) （马拉车）算法配合后缀数组（或配合哈希表）解决。

\(\text{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(\text{max right})\) 和 \(pos(\text{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;    }}

\(\text{Manacher}\) 算法进行 p[i]++ 时可以得到所有本质不同的回文串（不保证无重复）。

注意到一个与已经找过的串本质不同的回文串，一定能通过一次推动右端点得到，并且一次推动右端点最多增加一个回文串（如果以这个位置为右端点存在多个回文串，那么不是最长的串肯定在之前算过），这也同时证明了一个串内本质不同的回文子串是 \(O(n)\) 级别的。

那么可以利用 \(\text{Manacher}\) 求出若干个回文串，这一定包含了所有本质不同的回文子串，我们只用对它进行去重即可，后缀数组可以很方便的实现它，对长度相同的串，按 \(rk\) 进行排序，比较 \(\text{lcp}\) 是否为串长即可。

代码

#include
    
     #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
     
      inline bool chk_min(T &x,const _T y){return y
      
       
        inline bool chk_max(T &x,const _T y){return x
        
         >1]+1;        FOR(i,1,n)st[i][0]=arr[i];        FOR(j,1,18)FOR(i,1,n-(1<
         
          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\n",Ti,ans); } return 0;}