Displaying multiple substring indices within a string by using recursion

Question

def subStringMatchExact(target, key):

    if (target.find(key) == -1):
        return []
    else:
        foundStringAt = [target.find(key)]
        target = target[foundStringAt[0] + len(key):]
        return foundStringAt + subStringMatchExact(target, key)

string = subStringMatchExact("your code works with wrongly correlated coefficients which incorporates more costs", "co") 

print(string)

Current incorrect output:

[5, 22, 9, 19, 14]

I am having trouble summing the length of the substring on the previous recursion step. Like the second element of the list should be 29 instead of 22 as in len(previousSubstring) + len(key) - 1 + len(currentSubstring).

Any ideas to improve my code and/or fix my error too?

Answer 1

The fast way

You don't have to implement your own solution, its already done! Use the finditer function from the re module:

>>> import re
>>> s = 'your code works with wrongly correlated coefficients which incorporates more costs'
>>> matches = re.finditer('co', s)
>>> positions = [ match.start() for match in matches ]
>>> positions
[5, 29, 40, 61, 77]

Your own way

If you want to make your own implementation (using recursion) you could take advantage of the extra arguments of the str.find function. Lets see what help(str.find) says about it:

S.find(sub [,start [,end]]) -> int

    Return the lowest index in S where substring sub is found,
    such that sub is contained within s[start:end].  Optional
    arguments start and end are interpreted as in slice notation.

    Return -1 on failure.

There is an extra argument called start that tells str.find where to start searching the substring. That's just what we need!

So, modifying your implementation, we can get a simple, fast and beautiful solution:

def substring_match_exact(pattern, string, where_should_I_start=0):
    # Save the result in a variable to avoid doing the same thing twice
    pos = string.find(pattern, where_should_I_start)
    if pos == -1:
        # Not found!
        return []
    # No need for an else statement
    return [pos] + substring_match_exact(pattern, string, pos + len(key))

What is the recursion doing here?

• You're first searching the substring in the string starting at position 0.
• If the substring wasn't found, an empty list is returned [].
• If the substring was found, it will be returned [pos] plus all the positions where the substring will appear in the string starting at position pos + len(key).

Using our brand new function

>>> s = 'your code works with wrongly correlated coefficients which incorporates more costs'
>>> substring_match_exact('co', s)
[5, 29, 40, 61, 77]

Answer 2

Currently, your code is attempting to find the index of co in the shortened string, rather than the original string. Therefore, while [5, 22, 9, 19, 14] may seem incorrect, the script is doing exactly what you told it to do. By including an offset, like the script below, this code could work.

def subStringMatchExact(target, key, offset=0): # note the addition of offset

    if (target.find(key) == -1):
        return []
    else:
        foundStringAt = target.find(key)
        target = target[foundStringAt + len(key):]
        foundStringAt += offset # added
        return [foundStringAt] + subStringMatchExact(target, key, foundStringAt + len(key))
        # added foundStringAt + len(key) part

string = subStringMatchExact("your code works with wrongly correlated coefficients which incorporates more costs", "co") 
# no need to call w/ 0 since offset defaults to 0 if no offset is given

print(string)

I should add that making foundStringAt a list from the beginning isn't great practice when dealing with only one value, as you add some overhead with every [0] index lookup. Instead, since you want a list return type, you should just enclose it in [] in the return statement (as shown in my code).