blocks|key|4472874|text|def+sliding(a,+n):
++++return+(a[i:i%2Bn]+for+i+in+xrange(len(a)+-+n+%2B+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|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4472875|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>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
</code></pre>

blocks|key|4472291|text|这样做有效吗？|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4472292|def+count(string,+substring):
++++n+=+len(substring)
++++cnt+=+0
++++for+i+in+range(len(string)+-+n):
++++++++if+string[i:i%2Bn]+==+substring:
++++++++++++cnt+%2B=+1
++++return+cnt

print+count('ababaa',+'aba')+#+2|code-block|syntax|javascript|4472293|我不知道是否有更有效的解决方案，但这应该是可行的。|4472294|entityMap^0|0|0|0^^$0|@$1|2|3|4|5|6|7|K|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|L|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|M|8|@]|9|@]|A|$]]|$1|I|3|-4|5|6|7|N|8|@]|9|@]|A|$]]]|J|$]]

Does this do the trick?

<pre><code>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
</code></pre>

I don't know if there's a more efficient solution, but this should work.

blocks|key|4472853|text|在这里，使用re.finditer()是实现您想要的最好方法。|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4472854|import+re+

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

get_substring_count('ababaa',+'aba')
#+2+as+response|code-block|syntax|javascript|4472855|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/2/library/re.html#re.finditer^0|6|D|0|0|0^^$0|@$1|2|3|4|5|6|7|Q|8|@]|9|@$A|R|B|S|1|T]]|C|$]]|$1|D|3|E|5|F|7|U|8|@]|9|@]|C|$G|H]]|$1|I|3|-4|5|6|7|V|8|@]|9|@]|C|$]]]|J|$K|$5|L|M|N|C|$O|P]]]]

Here, using <a href="https://docs.python.org/2/library/re.html#re.finditer" rel="nofollow">re.finditer()</a> is the best way to achieve what you want.

<pre><code>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
</code></pre>

blocks|key|4472421|text|count+=+len(set([string.find('aba',x)+for+x+in+range(len(string))+if+string.find('aba',x)+>=+0]))|type|code-block|depth|inlineStyleRanges|entityRanges|data|syntax|javascript|4472422|unstyled|entityMap^0|0^^$0|@$1|2|3|4|5|6|7|G|8|@]|9|@]|A|$B|C]]|$1|D|3|-4|5|E|7|H|8|@]|9|@]|A|$]]]|F|$]]

<pre><code>count = len(set([string.find('aba',x) for x in range(len(string)) if string.find('aba',x) &gt;= 0]))
</code></pre>

blocks|key|4472935|text|下面是一个你可以使用的函数：|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4472936|def+count(haystack,+needle):
++++return+len([x+for+x+in+[haystack[i:j%2B1]+for+i+in+xrange(len(haystack))+for+j+in+xrange(i,len(haystack))]+if+x+==+needle])|code-block|syntax|javascript|4472937|然后：|4472938|>>>+count("ababaa",+"aba")
2|4472939|entityMap^0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|M|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|N|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|O|8|@]|9|@]|A|$]]|$1|I|3|J|5|D|7|P|8|@]|9|@]|A|$E|F]]|$1|K|3|-4|5|6|7|Q|8|@]|9|@]|A|$]]]|L|$]]

Here's a function you could use:

<pre><code>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])
</code></pre>

Then:

<pre><code>&gt;&gt;&gt; count("ababaa", "aba")
2
</code></pre>

blocks|key|4472542|text|循环遍历切分字符串|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4472543|def+count_substring(string,+sub_string):
++++l+=+len(sub_string)
++++n+=+len(string)
++++count+=+sum(1+for+i+in+range(n-l%2B1)+if+string[i:i%2Bl].count(sub_string)>0+)
++++return+count|code-block|syntax|javascript|4472544|entityMap^0|0|0^^$0|@$1|2|3|4|5|6|7|I|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|J|8|@]|9|@]|A|$E|F]]|$1|G|3|-4|5|6|7|K|8|@]|9|@]|A|$]]]|H|$]]

Looping through sliced string

<pre><code>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)&gt;0 )
 return count
</code></pre>

blocks|key|4472588|text|另一种考虑方式是利用Counter容器。虽然对于较短的字符串，公认的答案是最快的，但如果您在较长的字符串中搜索相对较短的子字符串，则计数器方法开始占据优势。此外，如果您需要对此进行重构以对相同的主字符串执行多个子字符串计数查询，则计数器方法看起来更有吸引力|type|unstyled|depth|inlineStyleRanges|entityRanges|offset|length|data|4472589|例如，搜索length+=3的子字符串，使用timeit得到以下结果；|4472590|主字符串长度/接受答案/计数器方法|4472591|6个字符/+4.1us+/+7.4us|4472592|50个字符/+24.4us+/+25us|4472593|150个字符/+70.7us+/+64.9us|4472594|1500个字符/+723us+/+614us|4472595|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%2Bsearch_len]+for+i+in+range(0,+len(main_string)+-+search_len+%2B+1)]
++++#Create+the+Counter+container
++++freq_count+=+Counter(candidates)
++++return+freq_count[search_string]|code-block|syntax|javascript|4472596|entityMap|0|LINK|mutability|MUTABLE|url|https://docs.python.org/2/library/collections.html^0|A|7|0|0|0|0|0|0|0|0|0^^$0|@$1|2|3|4|5|6|7|12|8|@]|9|@$A|13|B|14|1|15]]|C|$]]|$1|D|3|E|5|6|7|16|8|@]|9|@]|C|$]]|$1|F|3|G|5|6|7|17|8|@]|9|@]|C|$]]|$1|H|3|I|5|6|7|18|8|@]|9|@]|C|$]]|$1|J|3|K|5|6|7|19|8|@]|9|@]|C|$]]|$1|L|3|M|5|6|7|1A|8|@]|9|@]|C|$]]|$1|N|3|O|5|6|7|1B|8|@]|9|@]|C|$]]|$1|P|3|Q|5|R|7|1C|8|@]|9|@]|C|$S|T]]|$1|U|3|-4|5|6|7|1D|8|@]|9|@]|C|$]]]|V|$W|$5|X|Y|Z|C|$10|11]]]]

Another way to consider is by leveraging the <a href="https://docs.python.org/2/library/collections.html" rel="nofollow noreferrer">Counter</a> container. While the accepted answer is fastest for shorter strings, if you are searching relatively short substrings within long strings the Counter approach starts to take the edge. Also, if you have need to refactor this to perform multiple substring count queries against the same main string, then the Counter approach starts looking much more attractive

For example, searching for a substring of length = 3 gave me the following results using timeit;

Main string length / Accepted Answer / Counter Approach

6 characters / 4.1us / 7.4us

50 characters / 24.4us / 25us

150 characters / 70.7us / 64.9us

1500 characters / 723us / 614us

<pre><code>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]
</code></pre>

blocks|key|4472511|text|一种暴力的方法只是|type|unstyled|depth|inlineStyleRanges|entityRanges|data|4472512|n+=+len(needle)
count+=+sum(haystack[i:i%2Bn]+==+needle+for+i+in+range(len(haystack)-n%2B1))|code-block|syntax|javascript|4472513|(这是因为在Python中，对于大多数用途，包括数学，True和False等同于数字1和0+)。|offset|length|style|CODE|4472514|改用正则表达式，它可能是|4472515|count+=+len(re.findall(needle[:1]%2B"(?="%2Bre.escape(needle[1:])%2B")",
+++++++++++++++++++++++haystack))|4472516|(例如，使用a(?=ba)而不是aba来查找重叠匹配)|4472517|entityMap^0|0|0|R|4|W|5|16|1|18|1|0|0|0|6|7|G|3|0^^$0|@$1|2|3|4|5|6|7|U|8|@]|9|@]|A|$]]|$1|B|3|C|5|D|7|V|8|@]|9|@]|A|$E|F]]|$1|G|3|H|5|6|7|W|8|@$I|X|J|Y|K|L]|$I|Z|J|10|K|L]|$I|11|J|12|K|L]|$I|13|J|14|K|L]]|9|@]|A|$]]|$1|M|3|N|5|6|7|15|8|@]|9|@]|A|$]]|$1|O|3|P|5|D|7|16|8|@]|9|@]|A|$E|F]]|$1|Q|3|R|5|6|7|17|8|@$I|18|J|19|K|L]|$I|1A|J|1B|K|L]]|9|@]|A|$]]|$1|S|3|-4|5|6|7|1C|8|@]|9|@]|A|$]]]|T|$]]

A brute-force approach is just

<pre><code>n = len(needle)
count = sum(haystack[i:i+n] == needle for i in range(len(haystack)-n+1))
</code></pre>

(this works because in Python <code>True</code> and <code>False</code> are equivalent to numbers <code>1</code> and <code>0</code> for most uses, including math).

Using a regexp instead it could be

<pre><code>count = len(re.findall(needle[:1]+"(?="+re.escape(needle[1:])+")",
 haystack))
</code></pre>

(i.e. using <code>a(?=ba)</code> instead of <code>aba</code> to find overlapping matches too)

I want to find all the counts (overlapping and non-overlapping) of a sub-string in a string. 
I found two answers one of which is using regex which is not my intention and the other was much more in-efficient than I need.
I need something like:

<pre><code>'ababaa'.count('aba') == 2
</code></pre>

<code>str.count()</code> just counts simple substrings. What should I do?

Overlapping count of substring in a string in Python

容器

Python

我想找出一个字符串中一个子串的所有计数(重叠和非重叠)。我找到了两个答案，一个是使用正则表达式，这不是我的本意，另一个比我需要的效率低得多。我需要像这样的东西：'ababaa'.count('aba') == 2str.count()只计算简单的子字符串。我该怎么办？

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

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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

回答 8

Stack Overflow用户

Stack Overflow用户

Stack Overflow用户

社区

活动

资源

关于

腾讯云开发者

热门产品

热门推荐

更多推荐

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