题：https://vjudge.net/problem/URAL-1960
题意：给你一个长度为 n 的字符串 s，下标从 1 开始；
输出 n 个数，第 i 个数表示 1~i 内有多少个本质不同的回文串；
#include<iostream> #include<cstdio> #include<cstring> #include<algorithm> using namespace std; typedef long long ll; const int maxn=3e5+5; ll ans[maxn]; struct pam{ char s[maxn]; int tot;///构造的回文树共tot个节点，编号为0~tot-1，其中只有[2,tot-1]节点包含回文串!tot-2就是整个字符串本质不同的回文串个数 ! int last;///新添加一个字母后所形成的最长回文串表示的节点 int num[maxn];///num[i]:以“节点i所表示的回文串的结束字符”为结尾的回文串的个数 int cnt[maxn];///cnt[i]:节点i所表示的回文串在s中的总个数（建树时求出的不是完全的，最后统计一下才是正确的）非本质不同的 int son[maxn][30];///son[i][c]:i节点所表示的回文串两端增加字符c所表示的回文串所在的节点编号，如果不存在,son[i][c]=0 int fail[maxn];///fail[i]:节点i所表示的回文串的最长后缀回文串（不包括节点i本身）所在的节点编号，如果不存在,fail[i]=0 int len[maxn];///len[i]:节点i所表示的回文串的长度 int newNode(int Len){ for(int i=0;i<30;++i) son[tot][i]=0; cnt[tot]=0; num[tot]=0; fail[tot]=0; len[tot]=Len; return tot++; } int getFail(int p,int i){///类似KMP，失配后找一个尽量最长的后缀回文串 while(s[i-len[p]-1] != s[i]) p=fail[p]; return p; } void Init(){ s[0]='#';///添加一个s中不会出现的字符 tot=0; last=0; newNode(0); newNode(-1); fail[0]=1; } void solve(const char *buf){///个人习惯传入的数组buf下标从1开始 Init(); int n=strlen(buf+1); for(int i=1;i <= n;++i){ s[i]=buf[i]-'a'; int cur=getFail(last,i);///找到上一节点的最长回文后缀且这个回文串的开头字符是当前的s[i] ans[i]=ans[i-1]; if(!son[cur][s[i]]){///判断cur节点表示的回文串两端加入s[i]是否形成一个新的（本质不同）回文串 int now=newNode(len[cur]+2); fail[now]=son[getFail(fail[cur],i)][s[i]];///当前now的最长回文后缀就是cur的最长回文后缀再加上一个s[i] son[cur][s[i]]=now; num[now]=num[fail[now]]++; ans[i]++;///如果可以形成本质不同的字符串，ans[i]=ans[i-1]+1; } cnt[last=son[cur][s[i]]]++; } for(int i=tot-1;i>1;i--)///要把一个回文串里包含的回文串记录起来 cnt[fail[i]] += cnt[i]; } }PAM; char s[maxn]; int main(){ scanf("%s",s+1); PAM.solve(s); int len=strlen(s+1); // printf("Case #%d: %d ",++cas,ans[len]); for(int i=1;i <= len;++i) printf("%lld%c",ans[i],i == len ? ' ':' '); return 0; }