We wish to develop an algorithm to count the number of occurrences of a given substring in a given string. Substrings can overlap. For example, 'abababa' contains the substring 'bab' twice:

abababa

abababa

Outline in English an algorithm to count the number of occurrences of a given substring in a given string. An outline in English should not be program code or pseudo-code; see Section 6.4.1 for further guidance on outlining algorithms in English. Not using an English outline will lead to marks being deducted.

A problem definition has been provided below, which you can use to guide your solution.

Function: count substrings Inputs: main string, a string, substring, a string Preconditions: main string is a non-zero length string; substring is a non-zero length string at maximum the same length as main string Output: count, an integer Postconditions: count is the number of occurrences of substring within main string

*Write your answer here*

than:

Edit the code below to implement your algorithm outline from part (c)(i). You can use the tests below to test your code. The marker may run additional tests.

In [32]:

# *Write your code solution here*

def count_sub_strings(substring: str, main_string: str) -> int:

 pass # replace pass with your code

# Tests

%run -i m269_util

test_table = [

 ['None','abc','def',0],

 ['One','abc','xabcx',1],

 ['Two','abc','xabcxabc',2]

]

test(count_sub_strings, test_table)

None FAILED: None instead of 0 One FAILED: None instead of 1 Two FAILED: None instead of 2 Tests finished.