有没有比 count() 更快的方法来计算字符串中非重叠的出现次数？

Question

给定最小长度 N 和 1 和 0 的字符串 S（例如“01000100”），我试图 return 长度为 n 的子字符串的非重叠出现次数包含全部为“0”。例如，给定 n=2 和字符串“01000100”，非重叠“00”的数量为 2。

这是我所做的：

def myfunc(S,N):
  return S.count('0'*N)

我的问题：对于很长的字符串，是否有更快的方法来执行此操作？这是来自一个在线编码练习网站，我的代码通过了除一个测试用例之外的所有测试用例，该测试用例由于无法在时限内完成而失败。做一些研究似乎我只能发现 count() 是最快的方法。

Answer 1

这可能会更快：

>>> s = "01000100"
>>> def my_count( a, n ) :
...     parts = a.split('1')
...     return sum( len(p)//n for p in parts )
... 
>>> my_count(s, 2)
2
>>>

count() 的最坏情况是 O(N^2)，上面的函数是严格线性的 O(N)。这是 O(N^2) 数字来自的讨论：

此外，您可以始终手动执行此操作，而不使用 split()，只需遍历字符串，在 1 上重置计数器（一旦保存在 counter // n 某处）并增加计数器0。这肯定会击败任何其他方法，因为严格 O(N).

最后，对于相对较大的 n 值（n > 10 ?），可能有一个次线性（或仍然是线性的，但具有较小的常数）算法，它从比较 a[n-1] 到 0，然后回到开头。很有可能某处会有一个 1，所以如果 a[n-1] 是 1，我们就不必分析字符串的开头 - 仅仅是因为没有办法足够适合那里的零。假设我们在位置 k 找到了 1，下一个要比较的位置是 a[k+n-1]，再次回到字符串的开头。

这样我们可以在搜索过程中有效地跳过大部分字符串。

Answer 2

lenik post 做出了很好的回应，效果很好。我还发现了另一种比 count() 更快的方法，我也会在这里 post 。它使用正则表达式库中的 findall() 方法：

import re
def my_count(a, n):
  return len(re.findall('0'*n, a))

有没有比 count() 更快的方法来计算字符串中非重叠的出现次数？

Is there a faster way to count non-overlapping occurrences in a string than count()?

python

string

algorithm

counting