其中定义\(p[i]\)为以\(i\)为半径的回文半径，也就是从中心向两边最长能拓展多少，而根据这个可以推出来以它为中心的真正的回文串的长度。也就是\(p[i]-1\)，根据这个就可以得到最长的回文串的长度了。
但是复杂度为什么是\(O(n)\)呢，那么就涉及到了他的实现方法，我们定义一个回文中心\(C\)和这个回文的右侧\(R\)，也就是当前中心的最长回文的右端点，如果枚举到的\(i\)大于\(R\)，那么直接更新就行，但是如果在里边，那么会分出来三种情况：
\(1\)、枚举到的\(i\)关于\(C\)对称到\(i'\)，这时候\(i'\)的回文区域在\([L,R]\)，那么\(i\)的回文半径就是\(i'\):
证明：因为此时的\([L,R]\)就是一个回文区间，所以左右对称过来是一样的，所以得到\(i\)的回文半径。
\(2\)、枚举到\(i\)，此时对称点\(i'\)的回文区域超出了\(L\)，那么\(i\)的回文区域就一定是从\(i\)到\(R\)。
证明：借用一张图片便于解释：
（图好丑……）首先我们设\(L\)点关于\(i'\)对称的点为\(L'\)，\(R\)点关于\(i\)点对称的点为\(R'\)，\(L\)的前一个字符为\(x\)，\(L’\)的后一个字符为\(y\)，\(k\)和\(z\)同理，此时我们知道\(L - L'\)是\(i'\)回文区域内的一段回文串，故可知\(R’ - R\)也是回文串，因为\(L - R\)是一个大回文串。所以我们得到了一系列关系，\(x = y，y = k，x != z\)，所以 \(k != z\)。这样就可以验证出\(i\)点的回文半径是\(i - R\)。
\(3\)、\(i'\) 的回文区域左边界恰好和\(L\)重合，此时\(i\)的回文半径最少是\(i\)到\(R\)，回文区域从\(R\)继续向外部匹配。
证明：因为 \(i'\) 的回文左边界和L重合，所以已知的\(i\)的回文半径就和\(i'\)的一样了，我们设\(i\)的回文区域右边界的下一个字符是\(y\)，\(i\)的回文区域左边界的上一个字符是\(x\)，现在我们只需要从\(x\)和\(y\)的位置开始暴力匹配，看是否能把\(i\)的回文区域扩大即可。
小小总结一下，其实就是先进行暴力匹配，然后根据\(i'\)回文区域和左边界的关系进行查找。
例题+代码Manacher板子
#include<bits/stdc++.h> using namespace std; const int maxn = 11e6; char s[maxn]; int Manacher(char s[]){ int len = strlen(s); if(len == 0)return 0;//长度为0就return int len1 = len * 2 + 1; char *ch = new char[len1];//动态数组 int *par = new int[len1]; int head = 0; for(int i=0;i<len1;++i){ ch[i] = (i & 1) == 0 ? '#' : s[head++];//插入不一样的字符 } int C = -1; int R = -1; int Max = 0; par[0] = 1; for(int i=0;i<len1;++i){//枚举三种情况 par[i] = (i < R)? min(par[C*2-i],R-i) : 1;//取最小的回文半径 while(i + par[i] < len1 && i - par[i] > -1&& ch[i + par[i]] == ch[i - par[i]]){//暴力匹配 par[i] ++ ; } if(i + par[i] > R){//如果超过右边界就更新 R = i + par[i]; C = i; } Max = max(Max,par[i]);//更新最大半径 } delete[] ch;//清空动态数组 delete[] par; return Max - 1;//因为这个是添了字符的最大回文半径，所以回文串的最长是它-1 } int main(){ cin>>s; cout<<Manacher(s); return 0; } NO.3 KMP算法正常我们查找字符串是否为子串的时候，往往都是暴力枚举，效率为\(O(n^2)\)，但是字符串长了或者多了，肯定就是不行的了，所以有了\(KMP\)算法。
定义\(KMP\)算法是一种改进的字符串匹配算法，由\(D.E.Knuth，J.H.Morris\)和\(V.R.Pratt\)同时发现，因此人们称它为克努特——莫里斯——普拉特操作（简称\(KMP\)算法）。\(KMP\)算法的关键是利用匹配失败后的信息，尽量减少模式串与主串的匹配次数以达到快速匹配的目的。具体实现就是实现一个\(next\)函数，函数本身包含了模式串的局部匹配信息。时间复杂度\(O(m+n)\)。