寻找最长重复子串——Python

题目描述:

给定一个字符串,找出其中最长重复字串,以元组形式返回结果。例如,给定“aaaabb”,最长重复子串为“aaaa”,返回结果为(‘a’,4)。

解题思路:

将字符串中每个字符向后的重复次数列出,其中的最大值即为最长重复串的长度,对应的字符即为重复字符。例如:

a a a a b b

4 3 2 1 2 1

最大值为4,对应的字符为”a”

代码实现:

def longest_repetition(chars):
    if len(chars) == 0 or len(chars) == 1:
        return (chars,len(chars))
    result = [1]*len(chars)
    for left in xrange(len(chars)-1):
        for right in xrange(left+1, len(chars)):
            if chars[left] == chars[right]:
                result[left] += 1  
            else:
                break
    return (chars[result.index(max(result))], max(result))

# 测试用例
print longest_repetition("aaaabb")
print longest_repetition("cbdeuuu900")
print longest_repetition("")
print longest_repetition('ba')
print longest_repetition("bbbaaabaaaa")
print longest_repetition("abbbbb")
print longest_repetition("aabb")
print longest_repetition("a")

关于 “寻找最长重复子串——Python” 的 1 个意见

评论关闭。