马拉车算法代码实现示例

马拉车算法（Manacher's Algorithm）是一种用于求解字符串中最长回文子串的方法，它的主要特点是能够在线性时间内完成任务。本文将通过Python语言来实现马拉车算法，并提供一个具体的代码实例。

算法原理简介

马拉车算法的核心思想是利用已知的回文信息来减少不必要的比较次数。具体来说，当我们在处理某个字符时，可以利用其对称位置的信息来加速计算过程。通过在原字符串中插入特定的分隔符（如#），可以在处理过程中更方便地记录和更新最长半径。

示例代码实现

下面是马拉车算法的一个Python实现示例：

def manachers_algorithm(s):
    # 首先对输入字符串进行预处理，添加特殊字符
    t = '#'.join('^{}$'.format(s))
    n = len(t)
    p = [0] * n  # 记录每个位置的回文半径
    
    c = r = 0  # 中心点c和右边界r
    max_len, center_index = 0, -1  # 最长回文子串长度及其中心索引
    
    for i in range(1, n-1):
        if r > i:
            p[i] = min(r - i, p[2 * c - i])  # 利用对称性初始化p[i]
        
        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]
        
        # 记录最长回文子串
        if p[i] > max_len:
            max_len = p[i]
            center_index = i
    
    start = (center_index - 1 - max_len) // 2  # 转换为原字符串的起始索引位置
    return s[start:start + max_len]

# 测试代码
s = "babad"
result = manachers_algorithm(s)
print(f"输入字符串: {s}")
print(f"最长回文子串: {result}")

说明

1. 预处理：通过在原字符串中插入#来避免边界问题。
2. 中心扩展法：利用对称性质初始化每个位置的回文半径，并逐个字符进行检查和更新。
3. 记录最长回文子串：实时跟踪当前发现的最长回文子串及其起始索引。

通过上述代码，我们可以看到马拉车算法是如何在较短的时间内高效地求解最长回文子串问题。此方法适用于各种字符串处理场景，并且易于理解和实现。