CODEWITHSUNDEEP
python-3.xsubstring
Ayush Goyal
Ayush Goyal

Reputation: 233

How to count number of substrings in python, if substrings overlap?

The count() function returns the number of times a substring occurs in a string, but it fails in case of overlapping strings.

Let's say my input is:

^_^_^-_-

I want to find how many times ^_^ occurs in the string.

mystr=input()
happy=mystr.count('^_^')
sad=mystr.count('-_-')
print(happy)
print(sad)

Output is:

1
1

I am expecting:

2
1

How can I achieve the desired result?

Upvotes: 2

Views: 406

Answers (3)

Mad Physicist
Mad Physicist

Reputation: 114300

New Version

You can solve this problem without writing any explicit loops using regex. As @abhijith-pk's answer cleverly suggests, you can search for the first character only, with the remainder being placed in a positive lookahead, which will allow you to make the match with overlaps:

def count_overlapping(string, pattern):
    regex = '{}(?={})'.format(re.escape(pattern[:1]), re.escape(pattern[1:]))
    # Consume iterator, get count with minimal memory usage
    return sum(1 for _ in re.finditer(regex, string))

[IDEOne Link]

Using [:1] and [1:] for the indices allows the function to handle the empty string without special processing, while using [0] and [1:] for the indices would not.

Old Version

You can always write your own routine using the fact that str.find allows you to specify a starting index. This routine will not be very efficient, but it should work:

def count_overlapping(string, pattern):
    count = 0
    start = -1
    while True:
        start = string.find(pattern, start + 1)
        if start < 0:
            return count
        count += 1

[IDEOne Link]

Usage

Both versions return identical results. A sample usage would be:

>>> mystr = '^_^_^-_-'
>>> count_overlapping(mystr, '^_^')
2
>>> count_overlapping(mystr, '-_-')
1
>>> count_overlapping(mystr, '')
9
>>> count_overlapping(mystr, 'x')
0

Notice that the empty string is found len(mystr) + 1 times. I consider this to be intuitively correct because it is effectively between and around every character.

Upvotes: 3

ClumsyPuffin
ClumsyPuffin

Reputation: 4059

you can use regex for a quick and dirty solution :

import re
mystr='^_^_^-_-'
print(len(re.findall('\^(?=_\^)',mystr)))

Upvotes: 3

Sociopath
Sociopath

Reputation: 13401

You need something like this

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

mystr=input()
print(count_substr(mystr,'121'))

Input: 12121990

Output: 2

Upvotes: 1

Related Questions