在Python中找出字符串中的回文边界的程序

在计算机科学中，回文指正读和反读都相同的单词或短语，例如”racecar”、”refer”、”level”等。回文边界指字符串中从左往右遍历时回文的最大子字符串左端点和从右往左遍历时回文的最大子字符串右端点的交集。

在本文中，我们将介绍如何找出一个字符串的回文边界。

算法实现

方案1：暴力枚举

暴力枚举法是最简单的字符串算法，我们可以从字符串的第一个字符开始枚举左端点，再从字符串的最后一个字符开始枚举右端点，判断是否回文，如果是，则更新回文边界。

示例代码：

def find_palindromic_bounds(s: str) -> tuple:
    max_len = 0
    bounds = (0, 0)
    for i in range(len(s)):
        for j in range(len(s) - 1, i, -1):
            if s[i:j + 1] == s[i:j + 1][::-1] and j - i > max_len:
                max_len = j - i
                bounds = (i, j)
    return bounds

该算法的时间复杂度为 $O(n^3)$ ，空间复杂度为 $O(1)$ ，不适用于长字符串。

方案2：中心拓展

中心拓展法是一种优化后的暴力枚举法，我们可以从字符串的某个中心点开始往两端拓展，判断是否回文。为了考虑回文字符串长度的奇偶性，我们需要以每个字符和每两个相邻字符之间的空隙为回文中心点。

示例代码：

def find_palindromic_bounds(s: str) -> tuple:
    max_len = 0
    bounds = (0, 0)
    for i in range(len(s)):
        for j in [i, i + 1]:
            left, right = i, i
            while left >= 0 and right < len(s) and s[left] == s[right]:
                left -= 1
                right += 1
            if right - left - 2 > max_len:
                max_len = right - left - 2
                bounds = (left + 1, right - 1)
    return bounds

该算法的时间复杂度为 $O(n^2)$ ，空间复杂度为 $O(1)$ 。

方案3：马拉车算法

马拉车算法是一种较为高效的算法，主要利用回文子串的对称性和已知回文半径的信息，对回文半径的更新进行优化。

示例代码：

def find_palindromic_bounds(s: str) -> tuple:
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0] * n
    center = right = 0
    for i in range(1, n - 1):
        if right > i:
            p[i] = min(right - i, p[2 * center - i])
        while t[i + p[i] + 1] == t[i - p[i] - 1]:
            p[i] += 1
        if i + p[i] > right:
            center, right = i, i + p[i]
    left = (center - p[center]) // 2
    return left, left + p[center]

该算法的时间复杂度为 $O(n)$ ，空间复杂度为 $O(n)$ 。