一、啥是最长回文子串问题
咱先说说啥是回文串。回文串就是那种正着读和反着读都一样的字符串。比如说“level”“noon”，这些都是回文串。那最长回文子串问题呢，就是在一个给定的字符串里，找出最长的那个回文子串。
举个例子，有个字符串 “babad”，这里面最长的回文子串就是 “bab” 或者 “aba”。再比如 “cbbd”，最长回文子串就是 “bb”。这问题在很多实际场景里都能用到，像文本处理、生物信息学里分析 DNA 序列啥的。
二、传统方法解决最长回文子串问题
暴力枚举法
暴力枚举法就是把这个字符串里所有可能的子串都找出来，然后一个个判断是不是回文串，最后找出最长的那个。
下面是用 Python 实现的代码示例：
# 技术栈名称：Python
def longest_palindrome(s):
n = len(s)
max_length = 0
longest_substring = ""
# 遍历所有可能的子串起始位置
for i in range(n):
# 遍历所有可能的子串结束位置
for j in range(i, n):
sub_str = s[i:j + 1]
# 判断子串是否是回文串
if sub_str == sub_str[::-1]:
# 如果是回文串且长度大于当前最长长度
if len(sub_str) > max_length:
max_length = len(sub_str)
longest_substring = sub_str
return longest_substring
s = "babad"
print(longest_palindrome(s)) # 输出最长回文子串
暴力枚举法的时间复杂度是 $O(n^3)$，因为有两层循环来找出所有子串，判断子串是否是回文串又需要 $O(n)$ 的时间。空间复杂度是 $O(1)$，只用到了常数级的额外空间。
中心扩展法
中心扩展法就是以每个字符或者每两个相邻字符为中心，向两边扩展，看看能形成多长的回文串。
Python 代码示例如下：
# 技术栈名称：Python
def longest_palindrome(s):
if len(s) < 2:
return s
start, end = 0, 0
for i in range(len(s)):
# 以单个字符为中心扩展
len1 = expand_around_center(s, i, i)
# 以两个相邻字符为中心扩展
len2 = expand_around_center(s, i, i + 1)
max_len = max(len1, len2)
if max_len > end - start:
start = i - (max_len - 1) // 2
end = i + max_len // 2
return s[start:end + 1]
def expand_around_center(s, left, right):
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return right - left - 1
s = "babad"
print(longest_palindrome(s)) # 输出最长回文子串
中心扩展法的时间复杂度是 $O(n^2)$，因为要遍历每个字符，每个字符扩展的时间复杂度是 $O(n)$。空间复杂度是 $O(1)$。
三、Manacher 算法登场
算法核心思想
Manacher 算法的核心思想就是利用已经计算过的回文串信息，避免重复计算。它通过在字符串里插入特殊字符，把奇数长度和偶数长度的回文串统一处理，然后用一个数组来记录每个位置的回文半径。
具体步骤
- 插入特殊字符：在原字符串的每个字符前后都插入一个特殊字符，比如 “#”，这样能把奇数长度和偶数长度的回文串统一成奇数长度的回文串。例如，字符串 “abba” 会变成 “#a#b#b#a#”。
- 初始化变量：用一个数组
p来记录每个位置的回文半径，还有两个变量center和right分别记录当前最右回文串的中心位置和右边界。 - 遍历字符串：从左到右遍历字符串，对于每个位置
i，根据i和right的关系来计算p[i]。- 如果
i在right左边，就可以利用对称位置的信息来初始化p[i]。 - 如果
i在right右边，就只能从i开始向两边扩展来计算p[i]。
- 如果
- 更新
center和right：如果以i为中心的回文串右边界超过了right，就更新center和right。
Python 代码实现
# 技术栈名称：Python
def longest_palindrome(s):
# 插入特殊字符
t = '#'.join('^{}$'.format(s))
n = len(t)
p = [0] * n
c = r = 0
for i in range(1, n - 1):
i_mirror = 2 * c - i
if r > i:
p[i] = min(r - i, p[i_mirror])
else:
p[i] = 0
# 尝试扩展以 i 为中心的回文串
while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
p[i] += 1
# 如果以 i 为中心的回文串右边界超过了 r
if i + p[i] > r:
c = i
r = i + p[i]
# 找出最大的回文半径
max_len = 0
center_index = 0
for i in range(1, n - 1):
if p[i] > max_len:
max_len = p[i]
center_index = i
start = (center_index - max_len) // 2
return s[start:start + max_len]
s = "babad"
print(longest_palindrome(s)) # 输出最长回文子串
四、Manacher 算法复杂度分析
时间复杂度
Manacher 算法的时间复杂度是 $O(n)$，因为每个字符最多被访问两次。在遍历字符串的时候，利用对称位置的信息避免了很多重复计算。
空间复杂度
空间复杂度是 $O(n)$，主要是用来存储 p 数组。
五、应用场景
文本处理
在文本处理里，有时候需要找出最长的回文子串，比如在文学作品里找一些特殊的回文段落，或者在代码里找一些对称的代码片段。
生物信息学
在生物信息学里，DNA 序列可以看成是一个字符串，找出最长回文子串可以帮助分析 DNA 序列的结构和功能。
六、技术优缺点
优点
- 时间复杂度低：Manacher 算法的时间复杂度是 $O(n)$，比暴力枚举法和中心扩展法都快很多，在处理长字符串的时候优势明显。
- 统一处理奇偶长度回文串：通过插入特殊字符，把奇数长度和偶数长度的回文串统一处理，简化了算法逻辑。
缺点
- 空间复杂度较高：需要额外的 $O(n)$ 空间来存储
p数组。 - 理解难度较大：算法的核心思想和实现细节比较复杂，对于初学者来说不太容易理解。
七、注意事项
- 特殊字符选择：插入的特殊字符不能在原字符串里出现，不然会影响结果。
- 边界处理：在遍历字符串的时候，要注意边界条件，避免越界访问。
八、文章总结
Manacher 算法是一种非常高效的求解最长回文子串的算法，它利用已经计算过的回文串信息，避免了重复计算，把时间复杂度降到了 $O(n)$。虽然它的空间复杂度较高，理解难度也较大，但在处理长字符串的时候优势明显。在实际应用里，我们可以根据具体情况选择合适的算法来解决最长回文子串问题。
评论