查找字符串中每个子字符串的所有匹配项

Question

我试图找到主字符串（所有长度）中出现的所有子字符串。我的函数接受一个字符串，然后返回每个子字符串的字典（当然，它不止一次出现）以及它出现的次数（字典的格式：{substring: # of occurrences, ...}）。我正在使用collections.Counter(s)来帮助我。在

我的职能是：

from collections import Counter

def patternFind(s):
    patterns = {}
    for index in range(1, len(s)+1)[::-1]:
        d = nChunks(s, step=index)
        parts = dict(Counter(d))
        patterns.update({elem: parts[elem] for elem in parts.keys() if parts[elem] > 1})
    return patterns

def nChunks(iterable, start=0, step=1):
    return [iterable[i:i+step] for i in range(start, len(iterable), step)]

我有一个字符串，data，有大约2500个随机字母（按随机顺序）。但是，有2个字符串插入其中（随机点）。假设这个字符串是“TEST”。data.count('TEST')返回2。但是，patternFind(data)['TEST']给了我一个KeyError。因此，我的程序没有检测到其中的两个字符串。在

我做错了什么？谢谢！在

编辑：我创建测试实例的方法：

^{pr2}$

Answer 1

使用正则表达式

除了您描述的count()方法之外，regex是一个明显的替代方法

import re

needle = r'TEST'

haystack = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklagh'
pattern = re.compile(needle)

print len(re.findall(pattern, haystack))

捷径

如果您需要构建子字符串的字典，那么您可以只使用这些字符串的子集来实现这一点。假设您知道在data中要查找的needle，那么您只需要data的子串字典，这些子串的长度与{}相同。这很快。在

^{pr2}$

暴力：建立所有子串的字典

如果需要对所有可能的子字符串进行计数，此方法可行，但速度非常慢：

from collections import Counter

def gen_sub(s):
    for start in range(0, len(s)):
        for end in range(start+1, len(s)+1):
            yield s[start:end]

data = 'khjkzahklahjTESTkahklaghTESTjklajhkhz'
parts = Counter([sub for sub in gen_sub(data)])

print parts['TEST']

子串生成器改编自此：https://stackoverflow.com/a/8305463/1290420

Answer 2

虽然jurgenreza已经解释了为什么您的程序不起作用，但解决方案仍然相当缓慢。如果您只检查子串s，并且知道s[:-1]重复出现，那么您将得到一个更快的解决方案（通常快100倍甚至更多）：

from collections import defaultdict

def pfind(prefix, sequences):
    collector = defaultdict(list)
    for sequence in sequences:
        collector[sequence[0]].append(sequence)
    for item, matching_sequences in collector.items():
        if len(matching_sequences) >= 2:
            new_prefix = prefix + item
            yield (new_prefix, len(matching_sequences))
            for r in pfind(new_prefix, [sequence[1:] for sequence in matching_sequences]):
                yield r

def find_repeated_substrings(s):
    s0 = s + " "
    return pfind("", [s0[i:] for i in range(len(s))])

如果你想要口述，你可以这样称呼它：

^{pr2}$

在我的机器上，运行2247个元素需要0.02秒，而原始的（修正的）解决方案需要12.72秒。在

（请注意，这是一个相当幼稚的实现；使用索引而不是子字符串应该更快。）

编辑：以下变量适用于其他序列类型（不仅仅是字符串）。而且，它不需要哨兵。在

from collections import defaultdict

def pfind(s, length, ends):
    collector = defaultdict(list)
    if ends[-1] >= len(s):
        del ends[-1]
    for end in ends:
        if end < len(s):
            collector[s[end]].append(end)
    for key, matching_ends in collector.items():
        if len(matching_ends) >= 2:
            end = matching_ends[0]
            yield (s[end - length: end + 1], len(matching_ends))
            for r in pfind(s, length + 1, [end + 1 for end in matching_ends if end < len(s)]):
                yield r


def find_repeated_substrings(s):
    return pfind(s, 0, list(range(len(s))))

这仍然存在很长的子串将超过递归深度的问题。您可能需要捕获异常。在

Answer 3

在这里，您可以找到一个解决方案，它在string.find()周围使用递归包装器搜索主字符串中所有子字符串的出现。 collectallchuncks()函数返回一个defaultdict，其中所有的子字符串都是键，对于每个子字符串，都是在主字符串中找到子字符串的所有索引的列表。在

import collections

# Minimum substring size, may be 1
MINSIZE = 3

# Recursive wrapper
def recfind(p, data, pos, acc):
    res = data.find(p, pos)
    if res == -1:
        return acc
    else:
        acc.append(res)
        return recfind(p, data, res+1, acc)

def collectallchuncks(data):
    res = collections.defaultdict(str)
    size = len(data)
    for base in xrange(size):
        for seg in xrange(MINSIZE, size-base+1):
            chunk = data[base:base+seg]
            if data.count(chunk) > 1:
                res[chunk] = recfind(chunk, data, 0, [])
    return res

if __name__ == "__main__":
    data = 'khjkzahklahjTESTkahklaghTESTjklajhkhzkhjkzahklahjTESTkahklaghTESz'
    allchuncks = collectallchuncks(data)
    print 'TEST', allchuncks['TEST']
    print 'hklag', allchuncks['hklag']

编辑：如果只需要主字符串中每个子字符串的出现次数，则无需递归函数即可轻松获得：

^{pr2}$