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不会是任何⼦串在原始字符串中起始位置。

马拉松算法（Manachersalgorithm）（未完成）马拉松算法：马拉松算法是⽤来计算⼀个字符串中最长的回⽂字符串（对称字符串，如aba abba）。

⾸先，我们拿到⼀个字符串S，然后在S中的每个字符之间加#。

例如：S="abcb" T="a#b#c#b"我们T字符串的每⼀个T[i]向延伸d个字符使得 T[i-d,i+d]是⼀个回⽂字符串。

你会⽴刻发现，d就是以T[i]为中⼼的最长回⽂字符串的长度。

我们建⽴⼀个P数组，是的P数组的长度等于T的长度，每⼀个P[i]的值表⽰对应的T[i]为中⼼的最⼤回⽂字符串的长度。

如下：T = # a # b # a # a # b # a #P = 0103016103010瞅⼀下P，我们⽴刻就能发现最长的回⽂字符串长度是P[6]，对应字符串是"abaaba"。

你有没有发现，加⼊#之后以前的奇数回⽂字符串和偶数回⽂字符串都变得优雅了呢(提⽰：这仅仅是为了⽅便讲解，不是算法代码⾥所必须的步骤)。

现在，想象你在回⽂字符串"abaaba"的中间画⼀条线，你会发现P两边的数字也是关于这条线对称的。

不仅仅是这个字符串，你试试"aba"也是⼀样的情况。

这是巧合吗？答说是也是，说不是也不是。

这只是在某种条件下才会出现的，不管怎么样，我们已经取得了很⼤的进步。

让我们来看看更为复杂的字符串"babcbabcbaccba"。

上图展⽰⼀个从P基于T的⽣成过程，假设你已经完成P的⼀部分。

竖实线标记的是回⽂字符串"abcbabcba"的正中间C，两个竖虚线标记回⽂字符串的左边界和右边界。

你在i这个位置，且i位置关于C的镜像位置是i'。

你应该如何能快速计算出P[i]的值呢。

我们看到，i=13，i'=9，我们需要计算的是P[13]。

上图两个绿实线所覆盖的区域关于C对称。

马拉车算法（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。

算法练习题一、基础算法1. 编写一个程序，实现一个冒泡排序算法。

2. 实现一个选择排序算法。

3. 实现一个插入排序算法。

4. 编写一个函数，计算一个整数数组中的最大值和最小值。

5. 编写一个函数，实现二分查找算法。

6. 编写一个函数，实现快速排序算法。

7. 编写一个函数，判断一个整数是否为素数。

8. 编写一个函数，实现反转一个整数数组。

9. 编写一个函数，计算两个整数数组的交集。

10. 编写一个函数，判断一个字符串是否为回文。

二、数据结构11. 实现一个单链表的基本操作，包括插入、删除、查找。

12. 实现一个双向链表的基本操作，包括插入、删除、查找。

13. 实现一个栈的基本操作，包括压栈、出栈、查看栈顶元素。

14. 实现一个队列的基本操作，包括入队、出队、查看队首元素。

15. 实现一个二叉树的基本操作，包括插入、删除、查找。

16. 实现一个二叉搜索树的基本操作，包括插入、删除、查找。

17. 实现一个哈希表的基本操作，包括插入、删除、查找。

三、搜索与图论18. 编写一个程序，实现深度优先搜索（DFS）算法。

19. 编写一个程序，实现广度优先搜索（BFS）算法。

20. 编写一个程序，求解迷宫问题。

21. 编写一个程序，计算一个有向图的拓扑排序。

22. 编写一个程序，计算一个无向图的欧拉回路。

23. 编写一个程序，计算一个加权无向图的最小树（Prim算法）。

24. 编写一个程序，计算一个加权有向图的最短路径（Dijkstra算法）。

25. 编写一个程序，计算一个加权有向图的所有顶点对的最短路径（Floyd算法）。

四、动态规划26. 编写一个程序，实现背包问题。

27. 编写一个程序，计算最长公共子序列（LCS）。

28. 编写一个程序，计算最长递增子序列（LIS）。

29. 编写一个程序，实现编辑距离（Levenshtein距离）。

30. 编写一个程序，实现硬币找零问题。

31. 编写一个程序，实现矩阵链乘问题。

python 最大回文子串算法Python最大回文子串算法回文串是指正序和逆序相同的字符串，例如"level"和"noon"都是回文串。

在字符串处理中，求解最大回文子串是一种经典的问题，即找到给定字符串中最长的回文子串。

本文将详细介绍Python中常用的几种最大回文子串算法，包括简单的中心扩展法、动态规划法和马拉车算法。

1. 中心扩展法中心扩展法是最简单直观的求解最大回文子串的方法。

从左到右遍历字符串，以每个字符为中心向两边扩展，找到最长的回文子串。

具体实现如下：def expandCenter(s, left, right):while left >= 0 and right < len(s) and s[left] == s[right]:left -= 1right += 1return right - left - 1def longestPalindrome(s):start, end = 0, 0for i in range(len(s)):len1 = expandCenter(s, i, i) # 以字符为中心扩展len2 = expandCenter(s, i, i + 1) # 以空隙为中心扩展cur_len = max(len1, len2)if cur_len > end - start:start = i - (cur_len - 1) 2end = i + cur_len 2return s[start:end+1]这种方法的时间复杂度是O(n^2)，其中n是字符串的长度。

2. 动态规划法动态规划法也是常用的解决最大回文子串问题的方法。

采用二维的动态规划数组dp，其中dp[i][j]表示从第i个字符到第j个字符是否为回文串。

具体实现如下：def longestPalindrome(s):n = len(s)dp = [[False] * n for _ in range(n)]start, end = 0, 0for i in range(n):dp[i][i] = Trueif i < n - 1 and s[i] == s[i + 1]:dp[i][i + 1] = Truestart, end = i, i + 1for i in range(n - 1, -1, -1):for j in range(i + 2, n):if s[i] == s[j] and dp[i + 1][j - 1]:dp[i][j] = Trueif j - i > end - start:start, end = i, jreturn s[start:end + 1]动态规划法的时间复杂度同样为O(n^2)，但需要额外的O(n^2)空间来存储dp 数组。

回文的机趣及其应用
刘济民
【期刊名称】《阅读与写作》
【年(卷),期】1999(000)002
【摘要】回文有的书称回环,它是变换词语次序,使两个句子或词组,后者成为前者倒文的一种修辞方法。

前后的语词文字相同而词序相逆,排列整齐,变化有序,循环往复,增强了语言的回环美、变异美,灵活生动。

要选择这样的语言符号,构成回文修辞,需要有一定的语言修养,古今的文章中,人们都喜欢运用和阅读。

例如:
【总页数】2页(P20-21)
【作者】刘济民
【作者单位】
【正文语种】中文
【中图分类】H151
【相关文献】
1.成簇的规律间隔短回文重复序列/Cas9系统在病毒领域的应用 [J], 郑庆芬;段钟平;李建生
2.Manacher算法在计算最长回文子串长度中的应用 [J], 唐高阳
3.规律成簇间隔短回文重复-相关核酸内切酶9技术在基因组编辑和基因转录调控中的应用 [J], 管丽红;贾紫森;林俊堂
4.规律成簇间隔短回文重复-相关核酸内切酶9技术在基因组编辑和基因转录调控中的应用 [J], 管丽红;贾紫森;林俊堂
5.规律成簇间隔短回文重复序列及其相关蛋白基因编辑技术在感染性疾病诊断中的应用及其进展 [J], 于佳佳;张旭霞;李传友;刘毅;唐神结
因版权原因，仅展示原文概要，查看原文内容请购买。

manacher算法详解+模板manacher算法可以解决字符串的回⽂⼦串长度问题。

个⼈感觉szy学长讲的⾮常好，讲过之后基本上就理解了。

那就讲⼀下个⼈的理解。

（参考了szy学长的ppt）如果⼀个回⽂⼦串的长度是偶数，对称轴会落在两个字符中间。

⾸先两个字符中间的这个位置就很难表⽰。

所以我们在两个字符中间加上没有⽤的字符，⽐如说'#'。

开头结尾也加上。

例如：abcba --> #a#b#c#b#a#这样我们能很⽅便的表⽰每⼀个位置。

manacher算法最终的⽬的是求出⼀个数组pl[i]，代表以i为回⽂中⼼（也就是对称轴）的最长回⽂⼦串的回⽂半径。

回⽂半径指的是回⽂⼦串的长度除以⼆之后向上取整。

⽐如：#a#b#a#的回⽂半径就是4。

考虑⽤递推的⽅法求出pl数组。

⾸先我们知道pl[1]=1（特殊记⼀下）。

在递推的过程中维护⼀个np表⽰使i+pl[i]最⼤的⼀个i。

计算f[i]的时候，先考虑使⽤已知的信息求出f[i]。

如果i<=np+pl[np]，意味着i被以np为回⽂中⼼的最长回⽂⼦串“覆盖”了。

下⾯的图⽤红⾊表⽰以np为回⽂中⼼的最长回⽂⼦串，⽤绿⾊表⽰以i为回⽂中⼼的最长回⽂⼦串。

这时有两种情况：1.不仅i被覆盖，以i为回⽂中⼼的最长回⽂⼦串也被完全覆盖了。

这个时候由于对称性，pl[i]=pl[2*np-i]。

2.虽然i被覆盖，但是以i为回⽂中⼼的最长回⽂⼦串没有被完全覆盖。

这个时候我们只能保证np+pl[np]以内的对称性（蓝⾊部分）。

也就是说，pl[i]=pl[np]+np-i。

我们并不知道是哪种情况，所以只能对这两种情况分别求值并取其中的最⼩值。

之后如果还能继续向外拓展回⽂部分，就类似暴⼒的做法，⼀下⼀下向外拓展。

最后更新⼀下np。

求出的pl是适⽤于新串的（就是混了⼀堆‘#’的那个串）。

不难发现，对于原串，以i为中⼼的最长回⽂⼦串的长度为pl[i]-1，这个串的开始位置为(i-pl[i])/2+1（向下取整）。

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

例如，"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); }```在上述代码中，我们通过比较记录的最长回文半径和当前回文右边界和当前位置的距离，来寻找最长的回文半径，并更新回文中心和回文右边界的位置。

构造回文子串构造回文子串回文子串是指正读和反读都一样的字符串，比如“level”、“racecar”等等。

对于许多算法问题而言，都需要对输入的字符串进行回文子串的处理，因此如何快速构造回文子串成为了一个重要的课题。

下面将针对回文子串的构造方法进行分类介绍。

1. 中心扩展法中心扩展法是最简单、最直接的回文子串构造算法，其思路是将每一个字符作为中心向两侧扩展，并判断是否是回文子串。

该算法时间复杂度为O(n^2)，其中n为字符串长度。

2. 马拉车算法马拉车算法是一种高效的回文子串构造算法，其基本思想是通过已知回文子串的对称性进行快速扩展。

首先，在原字符串的每个位置插入一个不同的字符，用“#”分隔每个字符，得到一个新的字符串。

例如，原字符串“level”由此变成了“#l#e#v#e#l#”。

接下来，使用“Palindrome Array”数组记录以每个字符为基准可以扩展的最长回文子串的长度，同时记录此时最右侧的回文子串的边界R。

为了避免出界问题，可以在每个字符的左右两侧都加上无限制的字符（例如“#”），初始化Palindrome Array数组时，置所有的元素为0。

在计算过程中，可以首先通过对称性取得与当前字符i的对称点j的“Palindrome Array[i]”的值，然后将其与j到R这一部分的长度相加，得到以i为中心的最大回文子串长度，并更新Palindrome Array[i]的值。

最后，扫描整个Palindrome Array数组，取得最大值，并计算奇偶性确定回文子串的长度，从而在原字符串中找到构成回文子串的部分。

该算法的时间复杂度为O(n)，在处理大规模串的回文子串时，极具优势。

3. Manacher算法Manacher算法是对马拉车算法的一次改进，主要在寻找对称点上采用了更高效的方法。

Manacher算法在时间复杂度上与马拉车算法相同（O(n)），但更为简单直观。

Manacher算法仍然将原串插入分隔符“#”中，但是对Palindrome Array的计算过程采用了两个指针，分别指向一个最靠右的已知回文串，和一个最靠右的已知回文串的中心。

Manacher算法（马拉车）马拉车的解决的问题：给定字符串S，求S中的？解释：回⽂串就是正读反读都⼀样的字符串，⽐如奇回⽂串（bab）、偶回⽂串（noon）。

马拉车算法步骤：1）由于回⽂串存在奇回⽂串和偶回⽂串，马拉车算法第⼀步就是：预处理字符串，做法是在每⼀个字符的左右都加上⼀个特殊字符（前提是这个字符在字符串没有出现过），使这两种回⽂串都变成偶回⽂串。

⽐如加上’#’，这样奇回⽂串（bab）还是会变成奇回⽂串（#b#a#b#），偶回⽂串（noon）会变成奇回⽂串（#n#o#o#n#）。

2）然后我们定义⼀个辅助数组p⽤来表⽰经过与处理过的新字符串t，其中p[i]表⽰以字符t[i]为半径的回⽂⼦串长度，例如：index012345678910111213char$#1#2#2#1#2#2#R12125216123213）找规律规律①：最⼤半径减1等于最长回⽂串的长度看上⾯那个例⼦，以中间的 ‘1’ 为中⼼的回⽂⼦串 “#2#2#1#2#2#” 的半径是6，⽽未添加#号的回⽂⼦串为 “22122”，长度是5，为半径减1。

这是个普遍的规律么？我们再看看之前的那个 “#b#o#b#”，我们很容易看出来以中间的 ‘o’ 为中⼼的回⽂串的半径是4，⽽ "bob"的长度是3，符合规律。

再来看偶数个的情况 “noon”，添加#号后的回⽂串为 “#n#o#o#n#”，以最中间的 ‘#’ 为中⼼的回⽂串的半径是5，⽽ “noon” 的长度是4，完美符合规律。

所以我们只要找到了最⼤的半径，就知道最长的回⽂⼦串的字符个数了。

只知道长度⽆法定位⼦串，我们还需要知道⼦串的起始位置。

规律②：最长回⽂字符的起始位置是中间位置减去半径在除以2我们还是先来看中间的 ‘1’ 在字符串 “#1#2#2#1#2#2#” 中的位置是7，⽽半径是6，貌似 7-6=1，刚好就是回⽂⼦串 “22122” 在原串 “122122” 中的起始位置1。