最长回文字符串——马拉车算法
最长回文字符串
给定一个字符串 s，找到 s 中最长的回文子串。
示例 1：
输入:"babad"
输出:"bab"
注意:"aba" 也是一个有效答案。
示例 2：
输入:"cbbd"
输出:"bb"
解法有很多，①暴力破解法：可以枚举所有可能的字符串子串，然后判断是否为回文字符串。但这种解法的时间复杂度很高，首先是枚举所有可能的子串，时间复杂度O(n2)，再判断是否为回文字符串，时间复杂度为O(n2)，总体的时间复杂度为O(n3)。②反转法：将字符串反转，找出最长公共子串，注意这两段最长公共子串的位置应该是关于中心对称的，时间复杂度为O(n2)。③动态规划：动态规划最重要的就是要找到状态转移方程，而回文的最大特点就是如果一个子串是回文，它两侧的字符如果相同，那么加上这两个字符组成的新字符串同样也是回文，这种方法的时间复杂度同样也是O(n2)。④中心扩散法：遍历字符串中所有的字符，以这些字符为中心，用两个指针向外扩散，用一个数组来记录扩散的半径；这种方法使用起来有一个小缺陷，比如aba，abba两种回文，前者这种方法很好用，但是后者就需要特别去判断。为了解决这个问题，我们可以向每个字符之间插入一个相同的符号，比如#a#b#b#a#，这样就很好解决了上述问题，这种方法的时间复杂度也为O(n2)。这些方法的时间复杂度都在O(n2)以上，但有一种算法它的时间复杂度为O(n)，就是马拉车算法。
马拉车算法：
维基百科中对于 Manacher 算法是这样描述的：
[Manacher(1975)] 发现了一种线性时间算法，可以在列出给定字符串中从字符串头部开始的所有回文。并且，Apostolico, Breslauer & Galil (1995) 发现，同样的算法也可以在任意位置查找全部最大回文子串，并且时间复杂度是线性的。因此，他们提供了一种时间复杂度为线性的最长回文子串解法。替代性的线性时间解决 Jeuring (1994), Gusfield (1997)提供的，基于后缀树(suffix trees)。也存在已知的高效并行算法。
Manacher 算法本质上还是中心扩散法，只不过它使用了类似 KMP 算法的技巧，充分挖掘了已经进行回文判定的子串的特点，在遍历的过程中，记录了已经遍历过的子串的信息，也是典型的以空间换时间思想的体现。算法技巧：
①定义max_right来记录当前遍历字符串中能到达最右边的边界为多少，定义id记录达到最右边界的字符串中心
②算法步骤和中心扩散法一致，但是在计算类似#a#b#c#d#e#d#c#b#a#时，因为回文字符串左右对称，所以当你计算了左边的P数组的值时，右边的计算是可以借鉴左边的值，如下
文章图片
文章图片
文章图片
通过增加参数，降低寻找次数，是典型的以空间换取时间的做法。
def Manacher(s):#回文字符串线性时间复杂度
lenth =len(s)
if lenth <2:#特判
return s
t ="#"
for iin range(lenth):#初始化
t = t + s[i]
t = t +"#"
t_lenth =2 * lenth +1
p = [0 for i in range(t_lenth)]#记录扩散半径
max_right =0
id =0
max_lenth =0
start =1
for iin range(t_lenth):
if i < max_right:
mirror =2 * id - i
p[i] =min(p[mirror],max_right-i)
left = i - (1 + p[i])
right = i + (1 + p[i])
while left >=0 and right < t_lenthand t[left] == t[right]:
p[i] = p[i] +1
left = left -1
right = right +1
if i + p[i] > max_right:
max_right = i + p[i]
id = i
if p[i] > max_lenth:
max_lenth = p[i]
start = (i - max_lenth) //2
【最长回文字符串——马拉车算法】return s[start:start+max_lenth]
推荐阅读
- 一起来学习C语言的字符串转换函数
- 字符串拼接成段落，换行符（\n）如何只执行n-1次
- C语言的版本比较
- JavaScript|JavaScript — call()和apply()、Date对象、Math、包装类、字符串的方法
- backtracing——|backtracing—— 131. 分割回文串
- JS截取字符串的方法详解
- Python|Python 字符串 子串 回文串
- LeetCode|LeetCode 每日一题 [52] 表示数值的字符串
- LeetCode|LeetCode 336. 回文对 | Python
- Swift|Swift 字符串转数组