在一个字符串中找到相同的部分

Question

我有一个字符串，例如：abcgdfac

我想这样做： 输入：字符串，例如：

abcgdfabc

输出：dict（key是“words”，value是它出现的时间）

^{pr2}$

单词是单词的最大长度，它应该是贪婪的匹配。在

我花了很多时间在这上面，我想不通。 这串长度超过5000，它是一个基因组，我们想找出它之间的关系，第一次我们要找到这样一个dict，使数据更加清晰，有帮助。在

Answer 1

此正则表达式查找字母数字组，后跟任意数量的其他字符，然后再单独查找。然后，它在删除重复项的情况下遍历此列表，并给出这些字符组及其出现的次数：

import re

s = "eg,abcgdfabc"
for word in set(re.findall(r'(\w+)(\w*?\1)+', s)):
    print word, s.count(word)

印刷品

^{pr2}$

但是，如果我们不知道单词的确切含义，那么它只会在下面的字符串中找到一个重复的单词，尽管还有另一个候选词：

abcdeabcecd
abc  abc    <- this will be found
  cd     cd <- this won't be found

Answer 2

这里有一个丑陋的解决方案：

def parse(s,L=None):
    do_return=L is None
    if(not s):
        return
    if(do_return):
        L=[]
    substr=s[0]
    for i in range(1,len(s)-1):
        if s[:i] in s[i:]:
            substr=s[:i]
        else:
            L.append(substr)
            parse(s.replace(substr,''),L=L)
            break
    else:
        L.append(s)

    if(do_return):
        LL=[(ss,s.count(ss)) for ss in L] #Count the number of times each substring appears
        LLL=[]
        #Now some of our (unmatched) substrings will be adjacent to each other.
        #We should merge all adjacent unmatched strings together.
        while LL:
            LLL.append(LL.pop(0))
            while LLL[-1][1] == 1 and LL: #check if next is unmatched
                if(LL[0][1]==1): #unmatched, merge and remove
                    LLL[-1]=(LLL[-1][0]+LL[0][0],1)
                    LL.pop(0)
                else: #matched, keep on going.
                    break
        d={}
        for k,v in LLL:
            d[k]=v

        return d


S='eg,abcgdfabc'
print parse(S)  #{ 'e':1, 'g':2, ',':1, 'abc': 2, 'df', 1}

当然，这并不像您所期望的那样工作，因为g匹配两次（因为它是贪婪的）。。。在

如果您总是想以3人一组的方式进行迭代，这会变得更简单（更漂亮）：

^{pr2}$

Answer 3

如果您使用Python2.7+

>>> from itertools import islice
>>> from collections import Counter
>>> def split_steps(step, sequence):
...    it = iter(sequence)
...    bits = ''.join(islice(it,step))
...    while bits:
...        yield bits
...        bits = ''.join(islice(it,step))
...
>>> Counter(split_steps(3,'abcdgfabc')).most_common()
[('abc', 2), ('dgf', 1)]