问题描述：

在 Python 中，计算给定字符串出现次数（包括重叠）的最佳方法是什么？这是一种方法：

def function(string, str_to_search_for):
      count = 0
      for x in xrange(len(string) - len(str_to_search_for) + 1):
           if string[x:x+len(str_to_search_for)] == str_to_search_for:
                count += 1
      return count


function('1011101111','11')

此方法返回 5。

Python 中有没有更好的方法？

解决方案 1：

嗯，这可能更快，因为它在 C 中进行比较：

def occurrences(string, sub):
    count = start = 0
    while True:
        start = string.find(sub, start) + 1
        if start > 0:
            count+=1
        else:
            return count

解决方案 2：

>>> import re
>>> text = '1011101111'
>>> len(re.findall('(?=11)', text))
5

如果您不想将整个匹配列表加载到内存中，这永远不会是个问题！如果您真的想要，您可以这样做：

>>> sum(1 for _ in re.finditer('(?=11)', text))
5

作为一个函数（re.escape确保子字符串不会干扰正则表达式）：

def occurrences(text, sub):
    return len(re.findall('(?={0})'.format(re.escape(sub)), text))

>>> occurrences(text, '11')
5

解决方案 3：

您还可以尝试使用新的 Python regex 模块，它支持重叠匹配。

import regex as re

def count_overlapping(text, search_for):
    return len(re.findall(search_for, text, overlapped=True))

count_overlapping('1011101111','11')  # 5

解决方案 4：

Pythonstr.count计算不重叠的子字符串：

In [3]: "ababa".count("aba")
Out[3]: 1

这里列出了一些计算重叠序列的方法，我相信还有很多其他方法：)

前瞻正则表达式

如何用正则表达式找到重叠匹配？

In [10]: re.findall("a(?=ba)", "ababa")
Out[10]: ['a', 'a']

生成所有子字符串

In [11]: data = "ababa"
In [17]: sum(1 for i in range(len(data)) if data.startswith("aba", i))
Out[17]: 2

解决方案 5：

s = "bobobob"
sub = "bob"
ln = len(sub)
print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))

解决方案 6：

def count_substring(string, sub_string):
    count = 0
    for pos in range(len(string)):
        if string[pos:].startswith(sub_string):
            count += 1
    return count

这可能是最简单的方法。

解决方案 7：

一种相当 Python 化的方法是在这里使用列表理解，尽管它可能不是最有效的。

sequence = 'abaaadcaaaa'
substr = 'aa'

counts = sum([
    sequence.startswith(substr, i) for i in range(len(sequence))
])
print(counts)  # 5

该列表将是[False, False, True, False, False, False, True, True, False, False]由于它检查了字符串中的所有索引，并且因为int(True) == 1，所以sum给出了匹配的总数。

解决方案 8：

针对课程中提到的问题，我的回答是：

s = 'azcbobobegghaklbob'
total = 0
for i in range(len(s)-2):
    if s[i:i+3] == 'bob':
        total += 1
print 'number of times bob occurs is: ', total

解决方案 9：

如何在另一个重叠的字符串中查找模式

此函数（另一种解决方案！）接收一个模式和一个文本。返回一个列表，其中包含位于的所有子字符串及其位置。

def occurrences(pattern, text):
    """
    input: search a pattern (regular expression) in a text
    returns: a list of substrings and their positions 
    """
    p = re.compile('(?=({0}))'.format(pattern))
    matches = re.finditer(p, text)
    return [(match.group(1), match.start()) for match in matches]

print (occurrences('ana', 'banana'))
print (occurrences('.ana', 'Banana-fana fo-fana'))

[('ana', 1), ('ana', 3)]

[('Bana', 0), ('nana', 2), ('fana', 7), ('fana', 15)]

解决方案 10：

这里是我的 edX MIT “查找 bob” 解决方案（查找名为 s 的字符串中“bob”出现的次数），它基本上计算给定替换的重叠出现次数：

s = 'azcbobobegghakl'
count = 0

while 'bob' in s:
    count += 1 
    s = s[(s.find('bob') + 2):]

print "Number of times bob occurs is: {}".format(count)

解决方案 11：

另一种方法非常接近公认的答案，但是用作while测试if而不是包含if在循环内：

def countSubstr(string, sub):
    count = 0
    while sub in string:
        count += 1
        string = string[string.find(sub) + 1:]
    return count;

我认为这可以避免while True:并且更干净一些

解决方案 12：

如果字符串很大，则需要使用Rabin-Karp，总结一下：

• 子字符串大小的滚动窗口，在字符串上移动

• 添加和删​​除（即移动 1 个字符）的哈希开销为 O(1)

• 用 C 实现或依赖 pypy

解决方案 13：

可以使用正则表达式来解决。

import re
def function(string, sub_string):
    match = re.findall('(?='+sub_string+')',string)
    return len(match)

解决方案 14：

def count_substring(string, sub_string):
    counter = 0
    for i in range(len(string)):
        if string[i:].startswith(sub_string):
        counter = counter + 1
    return counter

上面的代码只是循环遍历字符串一次并不断检查是否有任何字符串以正在计算的特定子字符串开头。

解决方案 15：

re.subn尚未提及：

>>> import re
>>> re.subn('(?=11)', '', '1011101111')[1]
5

解决方案 16：

用替换字符串部分内容的解决方案

s = 'lolololol'
t = 0
t += s.count('lol')
s = s.replace('lol', 'lo1')
t += s.count('1ol')
print("Number of times lol occurs is:", t)

答案是 4。

解决方案 17：

def count_overlaps (string, look_for):
    start   = 0
    matches = 0

    while True:
        start = string.find (look_for, start)
        if start < 0:
            break

        start   += 1
        matches += 1

    return matches

print count_overlaps ('abrabra', 'abra')

解决方案 18：

函数以两个字符串作为输入，并计算 sub 在字符串中出现的次数（包括重叠）。为了检查 sub 是否为子字符串，我使用了in运算符。

def count_Occurrences(string, sub):
    count=0
    for i in range(0, len(string)-len(sub)+1):
        if sub in string[i:i+len(sub)]:
            count=count+1
    print 'Number of times sub occurs in string (including overlaps): ', count

解决方案 19：

对于重复的问题，我决定将其 3 乘 3 进行计数，然后比较字符串，例如

counted = 0

for i in range(len(string)):

    if string[i*3:(i+1)*3] == 'xox':
       counted = counted +1

print counted

解决方案 20：

这是另一个使用示例str.find()，但许多答案使其变得比必要的更复杂：

def occurrences(text, sub):
    c, n = 0, text.find(sub)
    while n != -1:
        c += 1
        n = text.find(sub, n+1)
    return c

In []:
occurrences('1011101111', '11')

Out[]:
5

解决方案 21：

鉴于

sequence = '1011101111'
sub = "11"

代码

在这个特殊案例中：

sum(x == tuple(sub) for x in zip(sequence, sequence[1:]))
# 5

更一般地，这

windows = zip(*([sequence[i:] for i, _ in enumerate(sequence)][:len(sub)]))
sum(x == tuple(sub) for x in windows)
# 5

或者扩展到发电机：

import itertools as it


iter_ = (sequence[i:] for i, _ in enumerate(sequence))
windows = zip(*(it.islice(iter_, None, len(sub))))
sum(x == tuple(sub) for x in windows)

选择

您可以使用more_itertools.locate：

import more_itertools as mit


len(list(mit.locate(sequence, pred=lambda *args: args == tuple(sub), window_size=len(sub))))
# 5

解决方案 22：

计算子字符串出现次数的一个简单方法是使用count()：

>>> s = 'bobob'
>>> s.count('bob')
1

replace ()如果您知道哪部分会重叠，您可以使用它来查找重叠的字符串：

>>> s = 'bobob'
>>> s.replace('b', 'bb').count('bob')
2

请注意，除了静态之外，还有其他限制：

>>> s = 'aaa'
>>> count('aa') # there must be two occurrences
1 
>>> s.replace('a', 'aa').count('aa')
3

解决方案 23：

def occurance_of_pattern(text, pattern):
    text_len , pattern_len = len(text), len(pattern)
    return sum(1 for idx in range(text_len - pattern_len + 1) if text[idx: idx+pattern_len] == pattern) 

解决方案 24：

我想看看相同前缀字符的输入数量是否与后缀相同，例如，"foo"但"""foo""失败了"""bar""：

from itertools import count, takewhile
from operator import eq


# From https://stackoverflow.com/a/15112059
def count_iter_items(iterable):
    """
    Consume an iterable not reading it into memory; return the number of items.

    :param iterable: An iterable
    :type iterable: ```Iterable```

    :return: Number of items in iterable
    :rtype: ```int```
    """
    counter = count()
    deque(zip(iterable, counter), maxlen=0)
    return next(counter)


def begin_matches_end(s):
    """
    Checks if the begin matches the end of the string

    :param s: Input string of length > 0
    :type s: ```str```

    :return: Whether the beginning matches the end (checks first match chars
    :rtype: ```bool```
    """
    return (count_iter_items(takewhile(partial(eq, s[0]), s)) ==
            count_iter_items(takewhile(partial(eq, s[0]), s[::-1])))

解决方案 25：

如果要计算长度为 5 的排列计数（如果需要不同的长度，请进行调整）：

def MerCount(s):
  for i in xrange(len(s)-4):
    d[s[i:i+5]] += 1
return d