题解 P3805 【【模板】manacher算法】

# 回文自动机 虽然过不去这个题目。。。但是没有回文自动机的模板题，拿这个题练练手也阔以$qwq$ ------------ [安利我的回文自动机日报](https://www.luogu.org/blog/zhouzhuo/qiang-shi-tu-xie-hui-wen-zi-dong-ji) 这个题目的话不要太模板 我们需要求出最长的回文串的长度，而我们知道，回文自动机的每个节点都代表一个回文串，日报里提及了 并且每个点我们都存了长度$len$，那么我们在新建节点的时候对新的回文串长度取$max$即可 接下来是美滋滋的代码时间~~~(只能得到$75$分，就把$75$分当做满分呗$qwq$) ~~~cpp #include<iostream> #include<cstdio> #include<cstring> #include<string> #define N 11000007 using namespace std; int n,last,cnt=1,ans; int len[N],ch[N][26],fail[N]; char s[N]; int main() { scanf("%s",s+1); n=strlen(s+1); s[0]='#'; fail[0]=1,len[1]=-1; for(int i=1;i<=n;++i) { int j; while(s[i]!=s[i-len[last]-1]) last=fail[last]; if(!ch[last][s[i]-'a']) { int now=++cnt; len[now]=len[last]+2; ans=max(ans,len[now]); j=fail[last]; while(s[i]!=s[i-len[j]-1]) j=fail[j]; fail[now]=ch[j][s[i]-'a']; ch[last][s[i]-'a']=now; } last=ch[last][s[i]-'a']; } printf("%d",ans); return 0; } ~~~