Manacher:
本质上与kmp无异，只是因为回文串的性质在具体操作上与kmp相比有较大区别
思想：充分利用已知信息
不妨假设我们已经求出了以id为中心的回文串长度为len[id](包括id)，且他是所有以得到信息中的lenmax=id+len[id]最大的,即他是能够延伸到最右边的回文中心，那么我们对于x>id，只需要分类讨论即可
1.x>=lenmax,我们只需要直接向右延伸
2.id<x<lenmax，我们直接利用已知信息（这个留给读者自己考虑），然后在向右延伸
综上由于lenmax的递增性，时间复杂度就为O(n)
代码：他咕了
PAM：
类比后缀自动机.....
我们考虑一个dfa
定义转移函数trans(s,c)表示在字符串s（某个状态）两边加上字符c所到的状态
由于回文串的长度有可能奇数也有可能是偶数
所以我们事先要考虑两个特殊点，即一个长度为0的节点，一个长度为-1的节点（为了方便——初始节点）
首先他与SAM不同的是，他是一颗树（不管有向边），且每一个节点仅仅对应一个原串的回文子串
结论：一个串s本质不同的回文子串的个数显然不会超过len(s)个
证明：考虑数学归纳法
对于串s,考虑在他后面加上字符c，那么最多会新增的回文子串必然是以新加入的c为结尾的最长回文后缀，考虑其正确性，由于非最长回文后缀必然可以由最长回文后缀对称翻转到串s中，所以其一定已经在串s中出现过。
证毕
构造：
首先对于字符串s我们考虑我们已经构造出了1....i的PAM，我们考虑在末尾加入字符c=s[i+1]
首先我们要找到以i+1为结尾最长回文子串，不妨假设s[l...i+1]为回文子串，那么根据回文串的性质s[l+1...i]也是回文子串（回文串的性质贯串PAM始终）
所以我们要找到以i结尾的最长回文子串且满足他的前驱为c
我们是不是还没有考虑fail指针？？？
fail[s]表示状态s(字符串)所指向的最长回文后缀
没错，这样我们就只需要沿着fail指针往上暴力跳就行了
复杂度对吗？
我们考虑势能分析
由于找以i结尾的最长回文子串且满足他的前驱为c的时间与找次长回文子串且满足他的前驱为c的时间复杂度同阶
所以我们只考虑第一个问题，首先定义len_max[i]表示以i结尾的最长回文串，那么我们显然有一个性质
len_max[i]+1>=len_max[i+1],所以就证完了
然后我们分析一下：
他能够整合一个串中的回文子串，而且关于字符串的性质（什么前缀后缀之类的）也能用fail指针来维护
比较优良的就在于他是一棵树,可操作空间大
至于具体用处，题目比较少，方法比较单调，我也不知道有什么广泛的应用
[APIO2014]回文串
// luogu-judger-enable-o2 #include<bits/stdc++.h> #define ll long long #define mk(x,y) make_pair(x,y) using namespace std; const int N=3e5+10; char s[N]; int ch[N][26]; int last,l,cnt; int fail[N]; vector<int>e[N]; ll len[N],sum[N]; ll ans; //1-odd 2-even void make_PAM(int i,char c) { int now=last; while (s[i-1-len[now]]!=c) {now=fail[now];} if (!ch[now][c-'a']) { ch[now][c-'a']=++cnt; len[cnt]=len[now]+2; sum[cnt]=1; last=cnt; if (now==1) { fail[cnt]=2; } else { now=fail[now]; while (s[i-1-len[now]]!=c) {now=fail[now];} fail[cnt]=ch[now][c-'a']; } } else { now=ch[now][c-'a']; sum[now]++; last=now; } } void init() { last=cnt=2; fail[2]=1; len[2]=0; len[1]=-1; } void dfs(int now) { int l=e[now].size(); for (int i=0;i<l;i++) { int u=e[now][i]; dfs(u); sum[now]+=sum[u]; } ans=max(ans,(long long)sum[now]*len[now]); } int main() { scanf("%s",s+1); l=strlen(s+1); init(); for (int i=1;i<=l;i++) { make_PAM(i,s[i]); } for (int i=1;i<=cnt;i++) if (fail[i]) e[fail[i]].push_back(i); dfs(1); printf("%lld\n",ans); }
