正題

題目鏈接:https://www.luogu.com.cn/problem/P5496

---

題目大意

長度為$n$的字符串，求每個字符串作為結尾有多少個回文串。

---

解題思路

$PAM$。

下面是個人對$PAM$的一些理解(不是講解)：

每個節點表示一個回文串，就是根到其的路徑上的字符為一半。

為了方便表示長度為奇數的和偶數的，這里用了兩個根節點。一個奇數根長度為$?1$，偶數根長度為$0$。偶數根的$fail$指向奇數根。

$fail$指針表示該回文串的最長回文后綴(不包括整串)

加入新節點時，在上個節點的基礎上不停的往后跳$fail$直到該回文串的前一個字符等于當且字符。

新節點的$fail$值同理在新點的父節點的$fail$上面跳$fail$。

時間復雜度$O(n)$，空間復雜度$O(nT)$

---

$code$

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2e6+10; int n,len[N],fail[N],num[N],next[N][26],cnt,m,last; char s[N]; int get_fail(int x){for(;s[n-len[x]-1]!=s[n];)x=fail[x];return x; } int Insert(){int x=get_fail(last);if(!next[x][s[n]]){len[++cnt]=len[x]+2;int y=get_fail(fail[x]);fail[cnt]=next[y][s[n]];num[cnt]=num[fail[cnt]]+1;next[x][s[n]]=cnt;}return (last=next[x][s[n]]); } int main() {scanf("%s",s+1);m=strlen(s+1);s[0]=26;len[1]=-1;fail[0]=cnt=1;int k=0;for(n=1;n<=m;n++){s[n]=(s[n]-'a'+k)%26;printf("%d ",k=num[Insert()]);} }

總結

以上是生活随笔為你收集整理的P5496-[模板]回文自动机【PAM】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。