如何在Python中找到String中重叠序列的数量？

Question

我有一个很长的序列,我想知道一些子序列在这个序列中出现的频率.

我知道string.count(s,sub),但它只计算非重叠序列.

是否存在也计算重叠序列的类似函数？

Answer 1

作为编写自己的搜索功能的替代方法,您可以使用该re模块:

In [22]: import re

In [23]: haystack = 'abababa baba alibababa'

In [24]: needle = 'baba'

In [25]: matches = re.finditer(r'(?=(%s))' % re.escape(needle), haystack)

In [26]: print [m.start(1) for m in matches]
[1, 3, 8, 16, 18]

以上打印出所有(可能重叠)匹配的起始位置.

如果您需要的只是计数,以下应该可以做到:

In [27]: len(re.findall(r'(?=(%s))' % re.escape(needle), haystack))
Out[27]: 5

Answer 2

一个简单易懂的方法是:

def count(sub, string):
    count = 0
    for i in xrange(len(string)):
        if string[i:].startswith(sub):
            count += 1
    return count

count('baba', 'abababa baba alibababa')
#output: 5

如果你喜欢简短的片段,你可以使它更不易读,但更聪明:

def count(subs, s):
    return sum((s[i:].startswith(subs) for i in xrange(len(s))))

这使用了Python可以像处理整数一样处理boolean的事实.