Count number of non-contiguous occurrences in string

Question

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.

Answer 1

A dynamic programming algorithm in $\mathcal{O}(|S| |T|)$ should do the trick.

Let's denote $S = s_1…s_m$ and $T = t_1…t_n$. For $0\leqslant i \leqslant m$, $0\leqslant j \leqslant n$, let $N(i, j)$ be the number of occurrences of $s_1…s_i$ in $t_1…t_j$. We have $N(0, j) = 1$ (by convention, for computation purposes), $N(i, j) = 0$ if $i > j$ and if $i, j>0$:

$$N(i, j) = \left\{\begin{array}{ll} N(i, j-1) & \text{if }s_i \neq t_j\\ N(i, j-1) + N(i-1,j-1) & \text{otherwise} \end{array}\right.$$ The idea is that a subsequence $s_1…s_i$ appears in $t_1…t_j$ if it appears in $t_1…t_{j-1}$ or if $s_1…s_{i-1}$ is a subsequence of $t_1…t_{j-1}$ and $s_i = t_j$.

Now you just have to compute $N(m, n)$ to get the answer you want.

Answer 2

I think this should do it (string indexes starts by 1):

stack = [1] // start iterating from T[1]
count = 0

while stack.length > 0
   while (stack.last <= T.length and T[stack.last] != S[stack.length])
      ++stack.last;
 
   if (stack.last <= T.length)
       if (stack.length == S.length)
          ++count
          ++stack.last
       else
          stack.push(stack.last + 1)
   else 
       stack.pop()
       ++stack.last

The idea is as follow:

• There's a stack where each "level" represents a letter in $S$ in the same order. So level 1 represents letter a in your example, level 2 letter b etc. The content of level $i$ is the index of an ocurrence of $S_i$ in $T$.
• The index that you store on each level of the stack must be bigger than the index on every lower lever.
• Each time you find an ocurrence of $S_i$ in $T$, let's call $j_i$ to its index, you assign $j_i + 1$ to the level $i + 1$ (you "push" $j_i + 1$ on the stack) and find the next ocurrence of $S_{i+1}$ in $T$ starting at position $j_i + 1$.
• Each time you find a new ocurrence at level $|S|$ you add $1$ to your counter.
• Each time you reach the end of $T$, you pop your stack, increase the index of the level that is now the last, and repeat.