# Count number of non-contiguous occurrences in string

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.

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.

• I see, this explains a lot. Thank you! Nov 23, 2022 at 12:40

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

stack =  // start iterating from T
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.
• nice. can you estimate the complexity of this approach? Nov 21, 2022 at 20:56
• 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|})$
– ABu
Nov 21, 2022 at 21:08