[Discussion] Re. Substring counting

[Mekire]

Did you read the top post?
In this version we are looking for subsequences, not substrings.

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"

I gave a couple sample input/outputs in the OP as well and Grib put them in unittests for convenience.

This is the template with tests:

Hide/Show

import unittest as ut


def subsequence_count(needle, haystack):
    """Your code here"""
    pass
 
 
class TestSubsequence(ut.TestCase):
    def test_banana(self):
        n = subsequence_count('an', 'banana')
        self.assertEqual(n, 3)
         
    def test_panama(self):
        n = subsequence_count('an', 'trans-Panamanian banana')
        self.assertEqual(n, 25)
 
    def test_nnn(self):
        n = subsequence_count('nnn', 'nnnnn')
        self.assertEqual(n, 10)
         
    def test_assesses(self):
        needle = "assessesassessesas"
        haystack = "assessesassessesassessesassessesassessesassesses"
        n = subsequence_count(needle, haystack)
        self.assertEqual(n, 7963870)

 
if __name__ == '__main__':
    ut.main()