[Discussion] Re. Substring counting

[Mekire]

That's pretty neat. Your recursive approach hurts my head.
I have trouble analyzing the runtime of recursive algorithms like this.

I want to say that it is O(n^m) but I'm not positive.
I base this on the idea that a run of size m,n takes:
T(m,n) = O(n) * T(m-1, n-1)
Not particularly confident in that though.

I did add a particularly pathological test however, and yours doesn't seem to manage it in a reasonable time

Output:
...
----------------------------------------------------------------------
Ran 3 tests in 346.731s

My approach went the dynamic programming route.

T[i, j] is the number of times needle[:i+1] occurs as a subsequence of haystack[:j+1] where T is our dynamic programming table.
This leads to the recursive problem definition:
T[i,j] = T[i,j-1] + T[i-1,j-1] if needle[i] == haystack[j] else T[i,j-1]

The algorithm ends up fairly straight forward from there just filling in the table row by row:

Hide/Show

import numpy as np
import unittest as ut


def subsequence_count(needle, haystack):
    n = len(haystack)
    m = len(needle)
    T = np.zeros((m+1, n+1), dtype=int)
    T[0,:] = 1
    for j,source in enumerate(haystack, start=1):
        for i,search in enumerate(needle, start=1):
            T[i,j] = T[i,j-1] + T[i-1,j-1] if source == search else T[i,j-1]
    return T[-1,-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_assesses(self):
        needle = "assessesassessesas"
        haystack = "assessesassessesassessesassessesassessesassesses"
        n = subsequence_count(needle, haystack)
        self.assertEqual(n, 7963870)
        
 
if __name__ == '__main__':
    ut.main()

The pathological test is added at the bottom.
Mine results in:

Output:
...
----------------------------------------------------------------------
Ran 3 tests in 0.003s

OK