出现多于一次的最长的子串

longest_repeating_substring.py

ALPHABETSIZE = 26


def get_index(c):
    return ord(c)-ord('a')


class PostfixTreeNode:
    def __init__(self):
        self.children = [None] * ALPHABETSIZE
        self.cnt = 0

    def insert(self, s, i):
        self.cnt += 1
        if i == len(s):
            if self.cnt > 1:
                return s
            else:
                return None
        idx = get_index(s[i])
        if not self.children[idx]:
            self.children[idx] = PostfixTreeNode()
        sub = self.children[idx].insert(s, i+1)
        if sub:
            return sub
        else:
            if self.cnt > 1:
                return s[:i]
            else:
                return None


def longest_repeating_substring(s):
    longest_substr = ""
    root = PostfixTreeNode()
    for i in range(len(s)-1):
        substr = root.insert(s[i:], 0)
        if substr and len(substr) > len(longest_substr):
            longest_substr = substr
    return longest_substr

s = "aababa"
print longest_repeating_substring(s)