动态规划与Manacher算法：最长回文子串的优化解法
在字符串处理领域，寻找最长回文子串是一个经典问题。回文串是指正读和反读都相同的字符串。例如，“abba”和“madam”都是回文串。在LeetCode等编程竞赛平台上，这个问题经常以动态规划（DP）和Manacher算法两种方式出现。本文将深入探讨这两种方法，并重点介绍Manacher算法的优化解法。
动态规划解法
基本思路
动态规划解法的基本思想是将问题分解为更小的子问题，并存储这些子问题的解以避免重复计算。对于最长回文子串问题，我们可以定义一个二维数组`dp`，其中`dp[i][j]`表示字符串`s`中从索引`i`到`j`的子串是否为回文串。
状态转移方程
- 如果`s[i] == s[j]`，则`dp[i][j] = dp[i+1][j-1]`。
- 否则，`dp[i][j] = false`。
代码实现
python
def longestPalindrome(s: str) -> str:
n = len(s)
if n == 0:
return ""
if n == 1:
return s
dp = [[False] n for _ in range(n)]
start = 0
max_len = 1
for i in range(n):
dp[i][i] = True
for i in range(n - 1, -1, -1):
for j in range(i + 1, n):
if s[i] == s[j]:
if j - i == 1 or dp[i + 1][j - 1]:
dp[i][j] = True
if j - i + 1 > max_len:
start = i
max_len = j - i + 1
return s[start:start + max_len]
时间复杂度
动态规划解法的时间复杂度为O(n^2)，空间复杂度也为O(n^2)。
Manacher算法
基本思路
Manacher算法是一种线性时间复杂度的算法，用于寻找最长回文子串。该算法的核心思想是将原字符串进行预处理，添加特殊字符，使得原字符串变为一个奇数长度的字符串，从而简化回文串的判断。
预处理
- 在原字符串的每个字符前后添加特殊字符``，例如，对于字符串`s = "abba"`，预处理后的字符串为`"abba"`。
- 在预处理后的字符串中，添加空格分隔每个字符，例如，`"abba"`。
算法步骤
1. 初始化一个数组`p`，用于存储以每个字符为中心的最长回文子串的长度。
2. 初始化两个变量`center`和`right`，分别表示当前已知的回文串的中心和右边界。
3. 遍历预处理后的字符串，对于每个字符：
- 如果当前字符在`right`范围内，则利用对称性，将`p[i]`设置为`min(right - i, p[2 center - i])`。
- 扩展以当前字符为中心的回文串，并更新`center`和`right`。
4. 找到`p`中的最大值，并返回对应的最长回文子串。
代码实现
python
def longestPalindrome(s: str) -> str:
if not s:
return ""
预处理字符串
t = "".join(f"^{s}$")
n = len(t)
p = [0] n
center = right = 0
for i in range(1, n - 1):
if i < right:
p[i] = min(right - i, p[2 center - i])
while t[i + 1 + p[i]] == t[i - 1 - p[i]]:
p[i] += 1
if i + p[i] > right:
center, right = i, i + p[i]
max_len = max(p)
start = (center - max_len) // 2
return s[start:start + max_len]
时间复杂度
Manacher算法的时间复杂度为O(n)，空间复杂度也为O(n)。
总结
本文介绍了两种寻找最长回文子串的方法：动态规划和Manacher算法。动态规划解法简单易懂，但时间复杂度较高；而Manacher算法则具有线性时间复杂度，是解决此类问题的优化解法。在实际应用中，根据具体需求选择合适的方法。
Comments NOTHING