[Discussion] Re. Substring counting

[Gribouillis]

Of course, dynamic programming is the correct solution. I improved it to use only a one dimensional array. This is a nice generalization of Pascal's triangle. Actually, Pascal's triangle implements the case where the alphabet has only one letter!

import unittest as ut

def subsequence_count(needle, haystack):
    T = [0 for x in needle]
    pairs = [(i, needle[i]) for i in range(len(needle)-1, -1, -1)]
    for source in haystack:
        for i, search in pairs:
            if source == search:
                T[i] += T[i-1] if i > 0 else 1
    return T[-1]


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()

I get

.  AutoExecution
....
----------------------------------------------------------------------
Ran 4 tests in 0.000s

OK