字符串回文：中心扩展与Manacher算法
字符串回文是一个经典的计算机科学问题，指的是一个字符串可以从前向后读和从后向前读都相同的特性。在LeetCode等编程竞赛平台上，字符串回文问题经常以不同的形式出现，如判断一个字符串是否是回文、找到字符串的最长回文子串等。解决这类问题，我们可以采用中心扩展法和Manacher算法两种方法。
中心扩展法
中心扩展法是一种简单直观的解决字符串回文问题的方法。其基本思想是：对于字符串中的每一个字符，将其视为回文的中心，然后向左右两边扩展，直到不再满足回文的条件为止。
代码实现
以下是一个使用中心扩展法判断字符串是否为回文的Python代码示例：
python
def is_palindrome(s: str) -> bool:
def expand_around_center(left: int, right: int) -> bool:
while left >= 0 and right < len(s) and s[left] == s[right]:
left -= 1
right += 1
return left + 1 >= right - 1
for i in range(len(s)):
奇数长度的回文
if expand_around_center(i, i):
return True
偶数长度的回文
if expand_around_center(i, i + 1):
return True
return False
分析
中心扩展法的时间复杂度为O(n^2)，空间复杂度为O(1)。对于较长的字符串，这种方法可能会比较慢。
Manacher算法
Manacher算法是一种更高效的解决字符串回文问题的算法。它通过预处理字符串，将原字符串转换为一个新的字符串，使得原字符串中的所有字符都位于新字符串的奇数位置，从而简化了回文子串的判断。
代码实现
以下是一个使用Manacher算法找到字符串最长回文子串的Python代码示例：
python
def longest_palindromic_substring(s: str) -> str:
预处理字符串
def preprocess(s: str) -> str:
return '^' + ''.join(s) + '$'
初始化
T = preprocess(s)
n = len(T)
P = [0] n
C = R = 0
Manacher算法
for i in range(1, n - 1):
i_mirror = 2 C - i
P[i] = (R > i) and min(R - i, P[i_mirror])
尝试扩展回文
while T[i + 1 + P[i]] == T[i - 1 - P[i]]:
P[i] += 1
更新中心点和右边界
if i + P[i] > R:
C, R = i, i + P[i]
找到最长回文子串的长度和起始位置
max_len, start = max((n, i) for i, n in enumerate(P))
return s[(start - max_len) // 2: (start + max_len) // 2]
分析
Manacher算法的时间复杂度为O(n)，空间复杂度为O(n)。这种方法在处理较长的字符串时，效率远高于中心扩展法。
总结
在解决字符串回文问题时，我们可以根据实际情况选择中心扩展法或Manacher算法。中心扩展法简单直观，但效率较低；而Manacher算法效率较高，但实现较为复杂。在实际应用中，我们需要根据问题的具体要求和数据规模来选择合适的算法。
扩展阅读
1. 《算法导论》 - Robert Sedgewick, Kevin Wayne
2. 《编程之美》 - 陈数，李开复
3. LeetCode官方文档 - https://leetcode-cn.com/
通过学习这些资料，我们可以更深入地理解字符串回文问题的解决方法，并在实际编程中灵活运用。
Comments NOTHING