3
$\begingroup$

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.

$\endgroup$
0

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
1
  • $\begingroup$ I see, this explains a lot. Thank you! $\endgroup$
    – Aishgadol
    Commented Nov 23, 2022 at 12:40
2
$\begingroup$

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.
$\endgroup$
2
  • 2
    $\begingroup$ nice. can you estimate the complexity of this approach? $\endgroup$
    – kodlu
    Commented Nov 21, 2022 at 20:56
  • 2
    $\begingroup$ This is equivalent to $|S|$ stacked loops where each loop starts at the current position of its above loop plus 1, and ends at $|T|$, so I guess $O(|T|^{|S|})$ $\endgroup$
    – ABu
    Commented Nov 21, 2022 at 21:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.