Python 中字符串中子字符串的重叠计数

Question

我想找到字符串中子字符串的所有计数（重叠和非重叠）。我找到了两个答案，其中一个是使用正则表达式，这不是我的本意，另一个比我需要的效率低得多。我需要这样的东西：

'ababaa'.count('aba') == 2

str.count() 只计算简单的子字符串。我该怎么办？

Answer 1

这样做有用吗？

def count(string, substring):
    n = len(substring)
    cnt = 0
    for i in range(len(string) - n):
        if string[i:i+n] == substring:
            cnt += 1
    return cnt

print count('ababaa', 'aba') # 2

我不知道是否有更有效的解决方案，但这应该可行。

Answer 2

在这里，使用re.finditer()是实现你想要的最好方法。

import re 

def get_substring_count(s, sub_s):
    return sum(1 for m in re.finditer('(?=%s)' % sub_s, s))

get_substring_count('ababaa', 'aba')
# 2 as response

Answer 3

def sliding(a, n):
    return (a[i:i+n] for i in xrange(len(a) - n + 1))

def substring_count(a, b):
    return sum(s == b for s in sliding(a, len(b)))

assert list(sliding('abcde', 3)) == ['abc', 'bcd', 'cde']    
assert substring_count('ababaa', 'aba') == 2

Answer 4

count = len(set([string.find('aba',x) for x in range(len(string)) if string.find('aba',x) >= 0]))

Answer 5

这是您可以使用的函数：

def count(haystack, needle):
    return len([x for x in [haystack[i:j+1] for i in xrange(len(haystack)) for j in xrange(i,len(haystack))] if x == needle])

然后：

>>> count("ababaa", "aba")
2

Answer 6

蛮力方法就是

n = len(needle)
count = sum(haystack[i:i+n] == needle for i in range(len(haystack)-n+1))

（这是有效的，因为在 Python 中，True 和 False 等同于数字 1 和 0 对于大多数用途，包括数学）。

改用正则表达式可以

count = len(re.findall(needle[:1]+"(?="+re.escape(needle[1:])+")",
                       haystack))

（即使用 a(?=ba) 而不是 aba 来查找重叠匹配项）

Answer 7

遍历切片字符串

def count_substring(string, sub_string):
    l = len(sub_string)
    n = len(string)
    count = sum(1 for i in range(n-l+1) if string[i:i+l].count(sub_string)>0 )
    return count

Answer 8

另一种考虑方法是利用 Counter 容器。虽然接受的答案对于较短的字符串是最快的，但如果您在长字符串中搜索相对较短的子字符串，则 Counter 方法开始占据优势。此外，如果您需要重构它以针对同一主字符串执行多个子字符串计数查询，那么 Counter 方法开始看起来更有吸引力

例如，使用 timeit 搜索长度为 3 的子字符串得到以下结果；

主要字符串长度/接受的答案/反方法

6 个字符/4.1us/7.4us

50 个字符/24.4us/25us

150 个字符/70.7us/64.9us

1500 个字符/723us/614us

from collections import Counter

def count_w_overlap(search_string, main_string):
    #Split up main_string into all possible overlap possibilities
    search_len = len(search_string)
    candidates = [main_string[i:i+search_len] for i in range(0, len(main_string) - search_len + 1)]
    #Create the Counter container
    freq_count = Counter(candidates)
    return freq_count[search_string]

Python 中字符串中子字符串的重叠计数

Overlapping count of substring in a string in Python

python

string

substring

count