动态规划与Manacher算法：求解最长回文子串问题
在字符串处理领域，寻找最长回文子串是一个经典的问题。回文串是指正读和反读都相同的字符串。例如，“abba”和“madam”都是回文串。在LeetCode等编程竞赛平台上，这个问题通常以动态规划或Manacher算法的形式出现。本文将围绕这一主题，深入探讨动态规划方法以及Manacher算法的原理和实现。
动态规划方法
基本思想
动态规划（Dynamic Programming，DP）是一种将复杂问题分解为更小、更简单的子问题，并存储这些子问题的解以避免重复计算的方法。对于最长回文子串问题，我们可以将其分解为以下子问题：
1. 对于字符串中的每个位置，判断它是否是回文串的中心。
2. 如果是，则根据其左右两侧的回文子串长度，确定当前回文子串的长度。
状态定义
定义`dp[i][j]`为字符串`s[0...n-1]`中从位置`i`到位置`j`的子串是否为回文串。如果`s[i...j]`是回文串，则`dp[i][j] = true`；否则`dp[i][j] = false`。
状态转移方程
- 如果`s[i] == s[j]`，则`dp[i][j]`取决于`s[i+1...j-1]`是否为回文串。
- 如果`s[i] != s[j]`，则`dp[i][j] = false`。
边界条件
- 对于长度为1的子串，`dp[i][i] = true`。
- 对于长度为2的子串，`dp[i][i+1] = (s[i] == s[i+1])`。
代码实现
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, max_len = 0, 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 max_len < j - i + 1:
start = i
max_len = j - i + 1
return s[start:start + max_len]
时间复杂度
动态规划方法的时间复杂度为O(n^2)，空间复杂度也为O(n^2)。
Manacher算法
基本思想
Manacher算法是一种线性时间复杂度的算法，用于寻找最长回文子串。该算法的核心思想是将原字符串进行预处理，添加特殊字符，将原字符串转换为新的字符串，然后利用对称性来求解最长回文子串。
预处理
1. 在原字符串的首尾添加特殊字符``，例如`abba`。
2. 在每个字符之间插入特殊字符`$`，例如`a$b$b$a$`。
状态定义
定义`p[i]`为以`pos[i]`为中心的最长回文子串的长度。
状态转移方程
- 如果`pos[i]`在`pos[l]`和`pos[r]`之间，则`p[i] = min(p[2 l - i], r - i]`。
- 如果`pos[i]`不在`pos[l]`和`pos[r]`之间，则`p[i] = 1`。
边界条件
- `p[0] = 0`，因为只有一个字符。
- `p[1] = 1`，因为两个字符组成的子串要么是回文串，要么不是。
代码实现
python
def longestPalindrome(s: str) -> str:
if not s:
return ""
预处理字符串
t = "".join(f"^{s}$")
n = len(t)
p = [0] n
center, right = 0, 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, center_index = max((p[i], i) for i in range(1, n - 1))
start = (center_index - max_len) // 2
return s[start:start + max_len]
时间复杂度
Manacher算法的时间复杂度为O(n)，空间复杂度也为O(n)。
总结
本文介绍了两种求解最长回文子串问题的方法：动态规划和Manacher算法。动态规划方法简单易懂，但时间复杂度较高；而Manacher算法具有线性时间复杂度，是解决此类问题的最优选择。在实际应用中，可以根据具体需求选择合适的方法。
Comments NOTHING