logo标签列表

在文件中查找最常见的子字符串模式

pythonstringalgorithmdata-structuressubstring
3

您被给定一个字符串，例如：

input_string = """
HIYourName=this is not true
HIYourName=Have a good day
HIYourName=nope
HIYourName=Bye!"""

在文件中找到最常见的子字符串。 这里的答案是“HiYourName=”。 需要注意的是，HiYourName=本身不是字符串中的“单词”，即它周围没有空格分隔。

因此，需要澄清的是，这不是最常见单词问题。

啊哈！是的，子字符串应该至少有6个字符的最小长度。 - user3897793
1
那么，现在我们手头有一个编程问题。请注意，无论你输入多长的字符串，返回的子字符串长度都将是精确的该长度，或者其中一个返回的子字符串将是这样的长度。您应该为此进行计划。 - TheSoundDefense
4个回答
4

这是一个简单的暴力解决方案：

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)

您的示例字符串的输出结果为：
Size:   1:  Occurrences:  10  Phrase: ' '
Size:   2:  Occurrences:   4  Phrase: 'Na'
Size:   3:  Occurrences:   4  Phrase: 'Nam'
Size:   4:  Occurrences:   4  Phrase: 'ourN'
Size:   5:  Occurrences:   4  Phrase: 'HIYou'
Size:   6:  Occurrences:   4  Phrase: 'IYourN'
Size:   7:  Occurrences:   4  Phrase: 'urName='
Size:   8:  Occurrences:   4  Phrase: ' HIYourN'
Size:   9:  Occurrences:   4  Phrase: 'HIYourNam'
Size:  10:  Occurrences:   4  Phrase: ' HIYourNam'
Size:  11:  Occurrences:   4  Phrase: ' HIYourName'
Size:  12:  Occurrences:   4  Phrase: ' HIYourName='
Size:  13:  Occurrences:   2  Phrase: 'e HIYourName='
1

另一种不使用导入的暴力方法：

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=
1
您可以在线性时间内构建一个后缀树或后缀数组（参见http://en.wikipedia.org/wiki/Suffix_tree及其中的链接），然后在构建后缀树之后，您还可以通过深度优先搜索以线性时间计算所有最长出现子字符串的前缀数（子字符串出现次数）信息，并将此信息存储在后缀树的每个节点中。然后，您只需要搜索树以找到子字符串的最大出现次数（线性时间），然后返回出现最多次数的最长子字符串（也是线性时间）。
0
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接