python实现求最长子串长度

给定一个字符串，求它最长的回文子串长度，例如输入字符串'35534321'，它的最长回文子串是'3553'，所以返回4。

最容易想到的办法是枚举出所有的子串，然后一一判断是否为回文串，返回最长的回文子串长度。不用我说，枚举实现的耗时是我们无法忍受的。那么有没有高效查找回文子串的方法呢？答案当然是肯定的，那就是中心扩展法，选择一个元素作为中心，然后向外发散的寻找以该元素为圆心的最大回文子串。但是又出现了新的问题，回文子串的长度即可能是基数，也可能好是偶数，对于长度为偶数的回文子串来说是不存在中心元素的。那是否有一种办法能将奇偶长度的子串归为一类，统一使用中心扩展法呢？它就是manacher算法，在原字符串中插入特殊字符，例如插入#后原字符串变成'#3#5#5#3#4#3#2#1#'。现在我们对新字符串使用中心扩展发即可，中心扩展法得到的半径就是子串的长度。

现在实现思路已经明确了，先转化字符串'35534321' ---->'#3#5#5#3#4#3#2#1#'，然后求出以每个元素为中心的最长回文子串的长度。以下给出python实现:

#!/usr/bin/python
# -*- coding: utf-8 -*-

def max_substr(string):
    s_list = [s for s in string]
    string = '#' + '#'.join(s_list) + '#'
    max_length = 0
    length = len(string)
    for index in range(0, length):
        r_length = get_length(string, index)
        if max_length < r_length:
            max_length = r_length
    return max_length

def get_length(string, index):
    # 循环求出index为中心的最长回文字串
    length = 0
    r_ = len(string)
    for i in range(1,index+1):
        if index+i < r_ and string[index-i] == string[index+i]:
            length += 1
        else:
            break
    return length

if __name__ == "__main__":
    result = max_substr("35534321")
    print result

更多相关文章

随机推荐