string计数与重叠的事件
计算给定string出现次数的最佳方法是什么，包括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') returns 5 ？
或者有没有更好的方法在Python？
那么，这可能会更快，因为它在C：
def occurrences(string, sub): count = start = 0 while True: start = string.find(sub, start) + 1 if start > 0: count+=1 else: return count
>>> import re >>> text = '1011101111' >>> len(re.findall('(?=11)', text)) 5
如果你不想把整个列表加载到内存中，那永远不会是一个问题！ 你可以这样做，如果你真的想要：
>>> sum(1 for _ in re.finditer('(?=11)', text)) 5
作为一个函数（ re.escape确保子string不会干扰正则expression式）：
>>> def occurrences(text, sub): return len(re.findall('(?={0})'.format(re.escape(sub)), text)) >>> occurrences(text, '11') 5
Python的str.count计算非重叠的子string：
In [3]: "ababa".count("aba") Out[3]: 1
这里有几个方法来计算重叠的序列，我敢肯定还有更多:)
预见正则expression式
如何find与正则expression式的重叠匹配？
In [10]: re.findall("a(?=ba)", "ababa") Out[10]: ['a', 'a']
生成所有子string
In [11]: data = "ababa" In [17]: sum(1 for i in range(len(data)) if data.startswith("aba", i)) Out[17]: 2
您也可以尝试使用支持重叠匹配的新Python正则expression式模块 。
import regex as re def count_overlapping(text, search_for): return len(re.findall(search_for, text, overlapped=True)) count_overlapping('1011101111','11') # 5
s = "bobobob" sub = "bob" ln = len(sub) print(sum(sub == s[i:i+ln] for i in xrange(len(s)-(ln-1))))
我的回答是关于球场上的bob问题：
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
如何在重叠的另一个string中find一个模式
这个function（另一个解决scheme！）会收到一个模式和一个文本。 返回一个列表，其中包含位于其位置的所有子string。
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）]
这里是我的edX麻省理工学院的“find bob”*解决scheme（*find一个名为s的string中的“bob”发生次数），它基本上计算了一个给定的substing的重叠事件：
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)
这可以使用正则expression式来解决。
import re def function(string, sub_string): match = re.findall('(?='+sub_string+')',string) return len(match)
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')
作为input两个string的函数，计算string中出现次数的次数，包括重叠。 为了检查sub是否是一个子string，我使用了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
对于一个重复的问题，我已经决定3和3比较string，例如
counted = 0 for i in range(len(string)): if string[i*3:(i+1)*3] == 'xox': counted = counted +1 print counted
另一个非常接近接受的答案，但作为iftesting，而不是包括if在循环内使用：
def countSubstr(string, sub): count = 0 while sub in string: count += 1 string = string[string.find(sub) + 1:] return count;
这样可以避免“ while True:在我看来，它更简洁一些
如果string很大，您想要使用Rabin-Karp ，总结：
- 子串大小的滚动窗口，移动到一个string上
- O（1）用于添加和移除的开销（即，移动1个字符）
- 在C中实现或依靠pypy
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
上面的代码只是简单地在整个string中循环一次，并不断检查是否有任何string是从正在计数的特定子string开始的。
sum([ 1 for _ in range(len(string)-len(str_to_search_for)+1) if string[_:_+len(str_to_search_for)] == str_to_search_for])
在列表理解中，我们用较小string长度的滑动窗口一次一个位置滑过较大的string。 我们可以通过从较大的string中减去较小string的长度来计算滑动计数。 对于每张幻灯片，我们将较大的string的部分与较小的string进行比较，如果find匹配，则在列表中生成1。 所有这些在列表中的总和将给我们find的总数。
如果要计算长度为5的排列计数（如果需要，可以根据不同的长度进行调整）：
def MerCount(s): for i in xrange(len(s)-4): d[s[i:i+5]] += 1 return d
