Given strings $S,T$ such that $n=|T|>|S|$ , I'd like an algorithm to count number of occurrences of $S$ in $T$ (as a subsequence), not necessarily contiguous.
Example: if $T=aababc, S=abc$, the algorithm should return $5$.
I've tried taking a suffix tree/ suffix array approach, only to realize that these tools are good for contiguous substrings but not for non-contiguous subsequences.
aababc , aababc , aababc , aababc , aababc
A problem that (might) kind of relate to this problem from what I know would be the maximal non-contiguous subarray problem, yet I do not know how to connect between these.