Manacher算法

[编程题]Manacher算法

热度指数：1092 时间限制：C/C++ 2秒，其他语言4秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

给定一个字符串str, 返回str中最长回文子串的长度

[举例]

str=“123”。其中的最长回文子串“1”或者“2”或者“3”，所以返回1。

str=“abc1234321ab”。其中的最长回文子串“1234321”，所以返回7。

[要求]

如果str的长度为N，解决原问题的时间复杂度都达到O(N).

输入描述:

输入为一个字符串str

输出描述:

输出一个整数表示最长回文子串的长度

示例1

输入

输出

示例2

输入

abc1234321ab

输出

备注:

设N表示输入字符串的长度
保证输入字符中只含有小写字母及数字

算法知识视频讲解

Python

errorplayer

def Manacher(long_str):
    # 插入特殊字符#
    long_str_list = list(long_str)
    long_str = '#' + '#'.join(long_str_list) + '#'
    len_long_str = len(long_str)
    R = -1
    C = -1
    _max_radius = 1
    _max_C = 0
    
    radius = [0] * len_long_str
    
    for idx in range(len(long_str)):
        radius[idx] = max(min(radius[2 * C - idx], R - idx), 1) if idx < R else 1
        while(idx + radius[idx] < len_long_str and idx - radius[idx] >= 0):
            if (long_str[idx + radius[idx]] == long_str[idx - radius[idx]]):
                radius[idx] += 1
            else:
                break
        if idx + radius[idx] > R:
            R = idx + radius[idx]
            C = idx
        if _max_radius < radius[idx]:
            _max_radius = radius[idx]
            _max_C = idx
        
    return long_str[_max_C - _max_radius + 1: _max_C + _max_radius].replace('#','')

password = input()
print(len(Manacher(password)))

发表于 2022-06-29 09:27:28 回复(0)