Skip to content

Instantly share code, notes, and snippets.

@senarukana
Created March 13, 2015 07:00
Show Gist options
  • Save senarukana/25b759f1ef1d28405dce to your computer and use it in GitHub Desktop.
Save senarukana/25b759f1ef1d28405dce to your computer and use it in GitHub Desktop.
出现多于一次的最长的子串
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)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment