如何用Python找出字符串中重叠序列的数量？

Question

我有一个很长的序列，我想知道里面某些子序列出现的频率。

我知道有一个叫做 string.count(s, sub) 的函数，但它只能计算不重叠的序列。

有没有类似的函数可以计算重叠的序列呢？

Answer 1

这应该能帮到你：

matches =[]
st = 'abababa baba alibababa'
needle = 'baba'
for i in xrange(len(st)-len(needle)+1): 
   i = st.find(needle,i,i+len(needle))
   if(i >= 0):
     matches.append(st.find(needle,i,i+len(needle)))
print(str(matches))

你可以在这里查看：http://codepad.org/pmkKXmWB

没有对长字符串进行性能测试，看看它是否足够高效，适合你的使用。

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可以把布尔值（真和假）当作整数来处理的特点。

Answer 3

如果你不想自己写搜索功能，可以使用 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