求回文子串 O(n) manacher算法

leetcode之最长回⽂⼦串Golang（马拉车算法Manacher‘sAlgorithm）最开始尝试的是暴⼒破解的⽅法求最长的回⽂⼦串，可是总是超时，因为暴⼒破解⽅法的时间复杂度是O(N3)然后去查了⼀下求回⽂⼦串的⽅法，发现了这个马拉车算法（Manacher's Algorithm）马拉车算法求最长的回⽂⼦串的时间复杂度是O(N)奇数化字符串回⽂字符串有奇偶两种形式：a aba bb abba所以为了避免我们在算法中对奇偶两种形式分开讨论，我们就将这两种形式都转化为奇数形式（也就是回⽂串的总的字符数是奇数个），⽅法就是在每个字符之间的空隙之间加⼊特殊字符，例如： a ==> #a#aba ==> #a#b#a#bb ==> #b#b#因为字符数加上他们之间的空隙数的总数总是为奇数（空隙数⽐字符数多⼀个，两个相邻的数字加起来和为奇数），所以通过这种⽅式，我们可以将字符串处理为总数为奇数回⽂串的半径通过上⾯我们的处理以后，我们在定义回⽂串的半径，也就是回⽂串长度的⼀半#a# ==> 半径为2#a#b#a# ==> 半径为4半径就是奇数回⽂串的长度加1，然后除以2得到的结果通过我们处理以后的回⽂串的半径，我们能够很容易的得到原来回⽂串的长度，原来回⽂串的长度就是处理后的回⽂串的半径减1，例如：#a# ==> 半径为2 ==> 原来回⽂串的长度为2-1=1#a#b#a# ==> 半径为4 ==> 原来回⽂串的长度为4-1=3#b#b# ==> 半径为3 ==> 原来回⽂串的长度为3-1=2有了回⽂串的长度，我们只需要知道在最开始的字符串中那个回⽂⼦字符串的起始的位置，我们就能够轻松求得回⽂⼦串，如图所⽰，第⼀⾏表⽰字符串中每个元素的下标，第⼆⾏是处理后的字符串，第三⾏表⽰以当前字符为中⼼的回⽂串的半径（例如以下标为1的b为中⼼的回⽂串是#b#，那么他的半径就是2）原始的字符串babb，对于原来是偶数的回⽂⼦串bb，如图所⽰，下标为6的#就是这个回⽂⼦串的中⼼，⽤下标6减去对应的半径3，结果为3，刚好是回⽂⼦串bb在原始字符串babb中的位置但是如果是原来是奇数的回⽂串，例如bab，那么中⼼字符在图中对应的就是下标为3的值，它的半径为4，如果相减就得到-1，显然这个-1不会是任何⼦串在原始字符串中起始位置。

马拉车算法（manacher）前⾔马拉车算法是⼀个能在线性时间能求出最长回⽂串长度的算法。

个⼈感觉和kmp也许有异曲同⼯之妙。

⾸先，我们的⽬标是求出最长回⽂⼦串的长度。

暴⼒相信⼤家都会，先是枚举L和R然后O(n)判断每个⼦串是否是回⽂串，总时间复杂度O(n3)。

稍微优化⼀下，枚举中间点mid,贪⼼地向两端扩展找到最长的len[i]，即以i为回⽂串中⼼的最⼤扩展长度。

当然，我们发现这样只能处理回⽂串长度为奇数的情况。

所以对于这个暴⼒，我们有了⼀个新思路：在两个相邻字符之间插⼊⼀个不会出现的字符。

⽐如aabba，我们把它变成#a#a#b#b#a#，这样每个点向两边扩展出的就⼀定是奇数长度的len[i]了。

于是这个暴⼒的时间复杂度就是O(n2)。

下⾯所使⽤的字符串也是经过了这样的变换的。

这也正打开了马拉车算法的⼤门。

众所周知，对暴⼒算法的优化是对重复计算的优化以及已知信息的利⽤。

先来看重复的计算。

在上⾯O(n2)的算法中，我们对很多⼦串进⾏了重复搜索，最明显的就是，假设i和j都在同⼀个回⽂⼦串内并且关于中⼼对称，那么len[j]>=len[i]。

这是显然的。

于是我们考虑设置⼀个变量mid，表⽰上⾯那个回⽂⼦串的中⼼，mr(maxright)表⽰这个回⽂⼦串的右端点。

哦对了，这个回⽂⼦串是当前右端点最⼤的回⽂⼦串，所以叫做maxright。

当我们⽬前遍历到的i是⼩于mr的时候，即下图这种情况。

如图，我们找到i的对称点i'，发现可以⽤ 2*mid-i得到，于是 len[i]=len[mid*2-i]，但是这个对称只在我们以mid为重⼼的回⽂串中可以⽤，所以 i+len[i]<=mr,len[i]<=mr-i，综合，len[i]=min(len[mid*2-i],mr-i)。

接下来是另⼀种情况，也就是i在mr的右边，i>=mr。

此时，我们没有多余的信息可以利⽤了，只能以i为重⼼开始和上⾯说的⼀样暴⼒地拓展找len[i]，那么此时我们的i就是新的mid，找到的i+len[i]就是新的mr。

左程云最长回文子串回文字符串是指正序和倒序读起来都一样的字符串。

例如，"level"和"radar"都是回文字符串。

回文字符串有很多应用场景，其中最长回文子串是非常重要的一种。

左程云在他的著作《算法面试通关宝典》中介绍了一种用Manacher 算法求解最长回文子串的方法。

这个算法的时间复杂度为O(n)，并且求出的最长回文子串的长度比暴力算法更准确。

Manacher算法的核心思想是将字符串可视化成一个由字符和分隔符组成的新字符串。

为了使得字符串能够处理所有情况，我们需要在字符串的开头和结尾加上两个不同的分隔符。

这个过程可以用以下代码实现:```string preProcess(string s) {int n = s.length();string ret = "^";for (int i = 0; i < n; i++)ret += "#" + s.substr(i, 1);ret += "#$";return ret;}```经过这个处理以后，字符串就有了如下的新形态:^#a#b#b#a#$0123456789我们可以从左到右遍历字符串，记录每个位置对应的最长回文半径p[i]。

在遍历的过程中，我们不断更新最右边的回文右边界R和当前的回文中心C，同时利用之前遍历到的位置的信息来初始化p数组的值。

具体的实现过程可以参考以下代码:```string longestPalindrome(string s) {string T = preProcess(s);int n = T.length(), C = 0, R = 0;int *P = new int[n];memset(P, 0, sizeof(int)*n);for (int i = 1; i < n-1; i++) {int i_mirror = 2*C-i; //相对于C的位置if (R > i) P[i] = min(R-i, P[i_mirror]);else P[i] = 0;while (T[i+1+P[i]] == T[i-1-P[i]]) P[i]++;if (i+P[i] > R) {C = i;R = i + P[i];}}int maxLength = 0, centerIndex = 0;for (int i = 1; i < n-1; i++) {if (P[i] > maxLength) {maxLength = P[i];centerIndex = i;}}delete[] P;return s.substr((centerIndex - maxLength - 1) / 2, maxLength); }```在上述代码中，我们通过比较记录的最长回文半径和当前回文右边界和当前位置的距离，来寻找最长的回文半径，并更新回文中心和回文右边界的位置。

Manacher算法详解ManacherManacher算法是⼀个⽤来查找⼀个字符串中的最长回⽂⼦串(不是最长回⽂序列)的线性算法。

它的优点就是把时间复杂度为O(n2)的暴⼒算法优化到了O(n)。

⾸先先让我们来看看最原始的暴⼒扩展，分析其存在的弊端，以此来更好的理解Manacher算法。

暴⼒匹配暴⼒匹配算法的原理很简单，就是从原字符串的⾸部开始，依次向尾部进⾏遍历，每访问⼀个字符，就以此字符为中⼼向两边扩展，记录该点的最长回⽂长度。

那么我们可以想想，这样做存在什么弊端，是不是可以求出真正的最长回⽂⼦串？答案是显然不⾏的，我们从两个⾓度来分析这个算法1.不适⽤于偶数回⽂串我们举两个字符串做例⼦，它们分别是 "aba"，"abba"，我们通过⾁眼可以观察出，它们对应的最长回⽂⼦串长度分别是3和4，然⽽我们要是⽤暴⼒匹配的⽅法去对这两个字符串进⾏操作就会发现，"aba" 对应的最长回⽂长是 "131"，"abba" 对应的最长回⽂长度是 "1111"，我们对奇数回⽂串求出了正确答案，但是在偶数回⽂串上并没有得到我们想要的结果，通过多次测试我们发现，这种暴⼒匹配的⽅法不适⽤于偶数回⽂串2.时间复杂度O(n2)这⾥的时间复杂度是⼀个平均时间复杂度，并不代表每⼀个字符串都是这个复杂度，但因为每到⼀个新位置就需要向两边扩展⽐对，所以平均下来时间复杂度达到了O(n*n)。

Manacher算法本质上也是基于暴⼒匹配的⽅法，只不过做了⼀点简单的预处理，且在扩展时提供了加速Manacher对字符串的预处理我们知道暴⼒匹配是⽆法解决偶数回⽂串的，可Manacher算法也是⼀种基于暴⼒匹配的算法，那它是怎么来实现暴⼒匹配且⼜不出错的呢？它⽤来应对偶数字符串的⽅法就是——做出预处理，这个预处理可以巧妙的让所有字符串都变为奇数回⽂串，不论它原本是什么。

ManachersAlgorithm马拉车算法这个马拉车算法 Manacher‘s Algorithm 是⽤来查找⼀个字符串的的线性⽅法，由⼀个叫 Manacher 的⼈在 1975 年发明的，这个⽅法的最⼤贡献是在于将时间复杂度提升到了线性，这是⾮常了不起的。

对于回⽂串想必⼤家都不陌⽣，就是正读反读都⼀样的字符串，⽐如 "bob", "level", "noon" 等等，那么如何在⼀个字符串中找出最长回⽂⼦串呢，可以以每⼀个字符为中⼼，向两边寻找回⽂⼦串，在遍历完整个数组后，就可以找到最长的回⽂⼦串。

但是这个⽅法的时间复杂度为 O(n*n)，并不是很⾼效，下⾯我们来看时间复杂度为 O(n)的马拉车算法。

由于回⽂串的长度可奇可偶，⽐如 "bob" 是奇数形式的回⽂，"noon" 就是偶数形式的回⽂，马拉车算法的第⼀步是预处理，做法是在每⼀个字符的左右都加上⼀个特殊字符，⽐如加上 '#'，那么bob --> #b#o#b#noon --> #n#o#o#n#这样做的好处是不论原字符串是奇数还是偶数个，处理之后得到的字符串的个数都是奇数个，这样就不⽤分情况讨论了，⽽可以⼀起搞定。

接下来我们还需要和处理后的字符串t等长的数组p，其中 p[i] 表⽰以 t[i] 字符为中⼼的回⽂⼦串的半径，若 p[i] = 1，则该回⽂⼦串就是 t[i] 本⾝，那么我们来看⼀个简单的例⼦：# 1 # 2 # 2 # 1 # 2 # 2 #1 2 1 2 5 2 1 6 1 2 3 2 1为啥我们关⼼回⽂⼦串的半径呢？看上⾯那个例⼦，以中间的 '1' 为中⼼的回⽂⼦串 "#2#2#1#2#2#" 的半径是6，⽽未添加#号的回⽂⼦串为"22122"，长度是5，为半径减1。

Manacher算法（马拉车算法）浅谈什么是Manacher算法？转载⾃百度百科Manachar算法主要是处理字符串中关于回⽂串的问题的，它可以在 O（n）的时间处理出以字符串中每⼀个字符为中⼼的回⽂串半径，由于将原字符串处理成两倍长度的新串，在每两个字符之间加⼊⼀个特定的特殊字符，因此原本长度为偶数的回⽂串就成了以中间特殊字符为中⼼的奇数长度的回⽂串了。

Manacher算法提供了⼀种巧妙的办法，将长度为奇数的回⽂串和长度为偶数的回⽂串⼀起考虑，具体做法是，在原字符串的每个相邻两个字符中间插⼊⼀个分隔符，同时在⾸尾也要添加⼀个分隔符，分隔符的要求是不在原串中出现，⼀般情况下可以⽤#号。

⼀句话概括就是求解关于回⽂字串的⼀个线性⽅法如何实现Manacher算法？字符串改装函数trans①使原字符串转换为奇数串我们可以发现回⽂串有以下特征①奇数串②偶数串其中不管奇数串还是偶数串只要每个字符后⾯加⼀个字符，再在开头加⼀个字符例如#会强制把他们都转换为奇数串例如bob->#b#o#b# dood->#d#o#o#d#并且他们的回⽂特性不变并且可以发现⼀个规律那就是回⽂半径-1就是最⼤字串的回⽂长度，例如#b#o#b#的最⼤回⽂字串长度为4-1=3,#d#o#o#d#的最⼤回⽂长度为5-1=4②确定回⽂起始位置的转换我们还可以发现这样⼀个规律，如果开头再添加⼀个字符（应该为⾮#）例如$ bob->\(#b#o#b# dood->\)#d#o#o#d# 那么他的回⽂起始位置就在（原来带#的字符串的中⼼的数组下标-原来的回⽂半径）/2例如$#b#o#b#的回⽂中⼼在（4-4）/2=0$#d#o#o#d#=(5-5)/2=0函数完整代码string trans(string a){string t="$#";//初始化开头for(int i=0;i<a.size();i++)//每个后⾯加⼀个#{t+=a[i];t+='#';}return t;//返回}回⽂半径数组p[i]的计算完全是下⾯这⼀⾏的精髓p[i] = mx > i ? min(p[2 * id - i], mx - i) : 1;⽬前还对这⼀⾏并不是很理解⽆法说明，但是可以记住这是⼀个规律完整代码（洛⾕模板题 P3805 【模板】manacher算法)#include <bits/stdc++.h>using namespace std;string trans(string a){string t="$#";//初始化开头for(int i=0;i<a.size();i++)//每个后⾯加⼀个#{t+=a[i];t+='#';}return t;//返回}int p[110000050];//开⼤⼀点开⼩了还reint main(){ios::sync_with_stdio(0);//关闭同步三步⾛cin.tie(0);cout.tie(0);string a,b;//输⼊原字符串cin>>a;b=a;a=trans(a);//转换int mx,id,rl,rc,ans=-1;for(int i=1;i<a.size();i++){p[i]=mx>i?min(p[2*id-i],mx-i):1;//求p[i]的初始值while(a[i+p[i]]==a[i-p[i]])//如果回⽂半径延伸可以的话，p[i]++p[i]++;if(mx<i+p[i])//如果具有回⽂性质的最右边界⼩于⽬前更新的回⽂半径 {mx=i+p[i];//更新右边界id=i;//更新回⽂⼦串的初始位置}ans=max(ans,p[i]-1);//寻找最⼤值}cout<<ans;/*输出回⽂⼦串cout<<"\n";for(int i=(id-ans)/2;i<ans;i++)cout<<b[i];cout<<"\n";*/}。

马拉车算法详解简述 Manacher算法，⼜称马拉车算法，它是⽤于求⼀个字符串的最长回⽂⼦串长度的算法，时间和空间复杂度为O(n)。

算法思想 求⼀个字符串的最长回⽂⼦串长度，我们如果⽤暴⼒来做，我们就要取出这个串的所有⼦串，然后判断这个⼦串是不是回⽂串，复杂度是n⽅的。

那么马拉车为何如此神奇能做到O(n)呢？ ⾸先我们来看这两个串：abba和abcba。

第⼀个串的回⽂中⼼在两个b之间，第⼆个串的回⽂中⼼为字符c，这样两种情况我们分类讨论太⿇烦了，所以我们考虑对原字符串进⾏⼀个字符填充，abba->@#a#b#b#a#，abcba->@#a#b#c#b#a#，这样他们都变成了奇数，讨论的情况就⼀致了。

设原字符串长度为len1，重构后长度为len2，则len2=len1*2+2且对于s[i]，它在重构后字符串的对应下标为i*2+2。

由此我们可以写出重定义字符串的代码： ⾸先我们规定⼏个变量的含义：len[i]为以i为中⼼点的最长回⽂序列的回⽂半径，po为当前中⼼点，p为当前回⽂⼦串的右边界。

我们可以得出，ans=len[i]-1，因为加⼊填充字符后的str的最长回⽂串为2*len[i]-1，⼜因为#号的个数⽐原字符多⼀个，所以#字符的总数为len[i]个，故原字符的最长回⽂⼦串为len[i]-1个。

当i<=p时，找到i相对于po的对称点j，如果len[j]<p-i,如下图： 由对称性得知，i和j左右的字符是⼀样的，所以len[i]=len[j]。

如果len[j]>=p-i，由对称性，说明以i为中⼼的回⽂串会扩散⾄p以外，⽽⼤于p部分的串我们还没⽤匹配，所以我们⼀个⼀个匹配，更新po和len[i]。

int getstr(){//重定义字符串，s 为原字符串，str 为新串,len 为s 串长度,返回新串长度int k=0,len=strlen(s);str[k ++]='@';for (int i=0;i<len;i++){str[k ++]='#';str[k ++]=s[i];}str[k ++]='#';return k;} 当i>p时，说明以i为中⼼的回⽂串⼀点都没匹配，就只能⽼⽼实实⼀个⼀个匹配了。

马拉车算法Manacher Algorithm算法，俗称马拉车算法，其时间复杂为O(n)。

该算法是利⽤回⽂串的特性来避免重复计算的。

在时间复杂度为O(n^2)的算法中，我们在遍历的过程要考虑到回⽂串长度的奇偶性，⽐如说“abba”的长度为偶数，“abcba”的长度为奇数，这样在寻找最长回⽂⼦串的过程要分别考奇偶的情况，是否可以统⼀处理了？⼀）第⼀步是改造字符串S，变为T，其改造的⽅法如下：在字符串S的字符之间和S的⾸尾都插⼊⼀个“#”，如：S=“abba”变为T="#a#b#b#a#" 。

我们会发现S的长度是4，⽽T的长度为9，长度变为奇数了！！S的长度为奇数时，S=“abcba”，变化为T=“#a#b#c#b#a#”，T的长度为11，所以我们发现其改造可以将字符串的长度变为奇数，这样就可以统⼀的处理奇偶的情况了。

⼆）第⼆步，为了改进回⽂相互重叠的情况，我们将改造完后的T[ i ] 处的回⽂半径存储到数组P[ i ]中(P[ i ]表⽰以字符T[ i ]为中⼼的最长回⽂字串的最端右字符到T[ i ]的长度)，这样最后遍历数组P，取其中最⼤值即可。

举⼀个简单的例⼦感受⼀下：数组P有⼀性质，P[ i ] - 1就是该回⽂⼦串在原字符串S中的长度，⾄于证明，⾸先在转换得到的字符串T中，所有的回⽂字串的长度都为奇数，那么对于以T[ i ]为中⼼的最长回⽂字串，其长度就为2*P[ i ]-1, 经过观察可知，T中所有的回⽂⼦串，其中分隔符的数量⼀定⽐其他字符的数量多1，也就是有P[ i ]个分隔符，剩下P[ i ]-1个字符来⾃原字符串，所以该回⽂串在原字符串中的长度就为P[ i ]-1。

另外，由于第⼀个和最后⼀个字符都是#号，且也需要搜索回⽂，为了防⽌越界，我们还需要在⾸尾再加上⾮#号字符，实际操作时我们只需给开头加上个⾮#号字符，结尾不⽤加的原因是字符串的结尾标识为'\0'，等于默认加过了。

左程云最长回文子串
回文串是指正着读和倒着读都一样的字符串，如“level”、“racecar”等。

而回文子串则是指在一个字符串中，连续的一段子串是回文串。

例如，在字符串“babad”中，最长的回文子串是“bab”或“aba”。

左程云是一位著名的算法工程师，他在《程序员代码面试指南》一书中提出了一种求解最长回文子串的算法。

这个算法被称为“Manacher算法”，它的时间复杂度为O(n)，是目前已知的最优解。

Manacher算法的核心思想是利用回文串的对称性，避免重复计算。

具体来说，它维护了一个“回文半径数组”，用来记录以每个字符为中心的最长回文半径。

在遍历字符串的过程中，它利用已经计算出来的回文半径，来快速计算当前字符的回文半径。

这样就避免了重复计算，从而达到了O(n)的时间复杂度。

Manacher算法的实现并不复杂，但是需要注意一些细节。

例如，为了方便处理奇偶性，我们需要在字符串中插入一些特殊字符，如“#”等。

另外，我们需要记录当前已知的最长回文子串的起始位置和长度，以便在遍历过程中更新它们。

Manacher算法的应用非常广泛，它可以用来解决很多字符串相关的问题，如最长回文子序列、最长公共子串等。

在实际应用中，我们可以将它用于字符串匹配、文本编辑器、数据压缩等领域。

Manacher算法是一种非常优秀的求解最长回文子串的算法，它的时间复杂度为O(n)，并且实现起来也比较简单。

如果你对字符串算法感兴趣，那么一定要学习一下这个算法，它一定会让你受益匪浅。