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

Question

你会得到一个像这样的字符串：

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

现在要找出这个字符串中最常见的子字符串。在这个例子里，答案是 "HiYourName="。需要注意的是，"HiYourName=" 本身并不是字符串中的一个“单词”，也就是说，它的两边没有空格分隔。

所以，简单来说，这个问题不是在找最常见的单词。

Answer 1

这个问题和http://acm.hdu.edu.cn/showproblem.php?pid=2459上的问题完全一样。解决这个问题的方法是使用后缀数组或者后缀树，并且要用到rmq（区间最小查询）。

Answer 2

这是另一种不使用任何导入的暴力破解方法：

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=

Answer 3

你可以用线性时间来构建一个后缀树或后缀数组，简单来说，就是把你的字符串变成一种特殊的结构（想了解更多可以看看这个链接）。在你建好后缀树之后，可以通过一种叫深度优先搜索的方法，在线性时间内计算所有最长出现的子串的前缀数量（也就是某个子串出现的次数），并把这些信息存储在后缀树的每个节点上。接下来，你只需要在树中查找，找到某个子串出现次数最多的情况（也是线性时间），然后返回那个出现次数最多的最长子串（同样是线性时间）。

Answer 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='