[Discussion] Re. Substring counting

[Mekire]

This would normally go in homework discussions, but as the user has already solved their problem there is no reason to not post publicly.

Original poster was asking how to find the number of times one string occurred as a substring in another string.
https://python-forum.io/Thread-Substring-Counting

Extend this to instead give an algorithm that finds the number of times one string occurs as a subsequence in another string.

Whereas a substring must be contiguous, a subsequence need not be, though it must still be in the correct order.

For example if we count occurrences of the subsequence "an" in "banana" we get 3.
Comprised of the following: "banana", "banana", "banana"

Algorithm should run in O(mn) time where m is the size of the string we are looking for and n is the size of the string we are looking in.

def subsequence_count(needle, haystack):
    """Your code here"""
    pass

print(subsequence_count("an", "banana")) # Should print 3
print(subsequence_count("an", "trans-Panamanian banana")) # Should print 25