s = """ HIYourName=this is not true HIYourName=Have a good day HIYourName=nope HIYourName=Bye!"""
def conseq_sequences(li):
seq = []
maxi = max(s.split(),key=len) # max possible string cannot span across spaces in the string
for i in range(2, len(maxi)+ 1): # get all substrings from 2 to max possible length
seq += ["".join(x) for x in (zip(*(li[i:] for i in range(i)))) if " " not in x]
return max([x for x in seq if seq.count(x) > 1],key=len) # get longest len string that appears more than once
print conseq_sequences(s)
HIYourName=
from collections import Counter
s = " HIYourName=this is not true HIYourName=Have a good day HIYourName=nope HIYourName=Bye!"
for n in range(1, len(s)):
substr_counter = Counter(s[i: i+n] for i in range(len(s) - n))
phrase, count = substr_counter.most_common(1)[0]
if count == 1: # early out for trivial cases
break
print 'Size: %3d: Occurrences: %3d Phrase: %r' % (n, count, phrase)
您可以在线性时间内用字符串构建后缀树或后缀数组(请参见http://en.wikipedia.org/wiki/Suffix_tree及其链接),然后在构建后缀树之后,您还可以通过线性时间中的深度优先搜索计算线性时间中所有最长子串的后缀前缀数(子字符串的出现次数),并将这些信息存储在后缀树中的每个节点上。然后,您只需要搜索树来找到子串的最大出现次数(线性时间),然后返回出现次数最大的子串(也是线性时间)。在
另一种没有进口的野蛮力量:
下面是一个简单的暴力解决方案:
示例字符串的输出为:
^{pr2}$相关问题 更多 >
编程相关推荐