python - 在字符串中找到相同的部分

Question

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

我想做以下事情：输入：一个字符串，例如：

abcgdfabc

输出：一个字典（键是“单词”，值是它出现的时间），

abc:2
gdf:1

words 是 "words" 的最大长度，它应该是贪婪匹配。

我花了很多时间在上面，无法弄清楚。字符串长度超过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)

印刷

abc 2

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

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 个为一组进行迭代，这会变得容易得多（也更漂亮）：

from collections import defaultdict
def parse(s,stride=3):
    d=defaultdict(lambda:0)
    while s:
        key=s[:stride]
        d[key]+=1
        s=s[stride:]

    #if you need a regular dictionary:  dd={}; dd.update(d); return dd      
    return d

Answer 3

如果您使用的是 Python 2.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)]