Calculate occurrences in the overlapping string

Question

would like to know how to make how many substring combinations is possible within a string, ex:

   string = 'abcdcdc'
   sub_string = 'cdc'

the returned value I want in this case, is 2, because the code should be able to verify how many combinations OF THE "cdc" WORD can be found inside the string.

The way I tried was like this:

string = input().strip()
sub_string = input().strip()

idx = 0
count_p = 0
count = 0
for i in list(string):
    if i in sub_string[idx]:
        count += 1
        idx += 1
        if idx == 2:
            idx = 0
        elif count == 3:
            count = 0
            count_p += 1

    else:
        count = 0

print(count_p)

I’ve tried everything but without success,I have no idea how to do it, I’ll be on hold, thanks guys!!!.

Answer 1

Your logic, though a little strange, is almost correct. The only problem is that due to overlapping substring occurrences in the string, its code is lost in the counters. You implemented that counter count_p be incremented only when count is 3, but as the last c of the first occurrence of substring also refers to the first c of the second occurrence, the count will only reach 2, but not 3, making the result only 1 and not 2, which would be expected.

To solve this, instead of you simply zeroing the counter when it reaches 3, you check which is the current character and, if it matches the first character of the substring, assign the value 1. So you will be counting twice the same character, what configures the override of substrings.

string = 'abcdcdc'
sub_string = 'cdc'

idx = 0
count_p = 0
count = 0
for i in list(string):
    if i in sub_string[idx]:
        count += 1
        idx += 1
        if idx == 2:
            idx = 0
        elif count == 3:
            count = 0 if i != 'c' else 1
            count_p += 1

    else:
        count = 0


print(count_p)

^{See working on Ideone | Repl.it}

Caveats

1. You don’t need to convert the string to a list to run it with the for. In Python, the string type is eternal by nature, so just do: for i in string;

2. Your code reads from the user the string and the substring, but the logic is restricted to the example you gave, using the string 'abcdcdc' and substring 'cdc'. With different values, the program will probably not work;

Alternatives

Method str.find

Another way to solve the problem is to use the method find string. The method returns the start position of the occurrence or -1 if it does not exist. It is also possible to set the beginning of where the string will be considered to prevent it from counting twice the same occurrence. An example would be:

string = 'abcdcdc'
sub_string = 'cdc'

start = count = 0
while True:
    index = string.find(sub_string, start)
    if index >= 0:
        start = index + 1
        count += 1
    else:
        break

print(count)

^{See working on Ideone | Repl.it}

Regular expression

You can also use regular expressions to get all substring occurrences and count how many were. See an example:

import re

string = 'abcdcdc'
sub_string = 'cdc'

count = len(re.findall('(?=%s)' % sub_string, string))

print(count)

^{See working on Ideone | Repl.it}

Go through the string and compare substrings

You can also go through the entire string and check that the substring of the same size is equal to the substring you are looking for.

string = 'abcdcdc'
sub_string = 'cdc'

count = 0
for i in range(len(string)):
    if string[i:i+len(sub_string)] == sub_string:
        count += 1

print(count)

^{See working on Ideone | Repl.it}