How many ways can given subsequence occur in given sequence? Let me know if this task has already been posed. I haven't found it when I looked.

Input

master sequence \$\ X = x_1\dots x_n\$: sequence of characters, eg. \$\rm international\$
subsequence \$\ Y = y_1\dots y_m\$: sequence of characters, eg. \$\rm intl\$


Output
Number of possible mappings \$\mu: [1\dots m] \rightarrow [1\dots n]\$ of positions in subsequence to positions in the master sequence, such that for all \$j\in[1\ldots m]\$:

\$y_j = x_{\mu(j)}\$, viz. an occurrence of a character in the subsequence maps to an occurrence of the same character in the master sequence

\$\forall\ i \lt j:\ \mu(i) \lt \mu(j)\$, viz. the mapping preserves mutual position of character occurrences.


In the example above, there are 3 possible mappings:

\$\rm\underline{int}ernationa\underline{l}\$
\$\rm\underline{in}terna\underline{t}iona\underline{l}\$
\$\rm\underline{i}nter\underline{n}a\underline{t}iona\underline{l}\$


Rules
Lowest average asymptotic time complexity with respect to \$n+m\$ wins.
If it helps you, you can assume the input is a sequence of bytes (values 0-255).

Test cases
master sequence, subsequence -&gt; number of possible mappings
international, intl -&gt; 3
aaabbb, ab -&gt; 9
aaabbb, aabb -&gt; 9
only one, onl -&gt; 1
none, en -&gt; 0
Ruby, \$\mathcal{O}(nm)\$

I think I got the analysis for this right. Should be \$\mathcal{O}(nm)\$ because for each of the \$n\$ characters in the master sequence, it goes through at most \$m\$ steps to check each character of the subsequence (if they are all the same character). It's also optimized to try to be \$\Omega(n+m)\$ best case complexity, which occurs if all the characters in the subsequence are unique.



def submap master, sub
  subIndex = Hash.new{ |hash, key| hash[key] = [] }

  sub.chars.map.with_index do |c, i|
    subIndex[c] &lt;&lt; i
  end

  subCount = [0] * sub.length

  master.chars do |c|
    indices = subIndex[c]
    indices.reverse_each do |i|
      subCount[i] += i &gt; 0 ? subCount[i-1] : 1
    end
  end
  return subCount[-1]
end


Try it online!

Explanation

Define the function \$f(X_i,Y_j)\$ as the number of occurrences of the subsequence \$Y_j=y_1...y_j\$ in the sequence \$X_i=x_1...x_i\$. In this situation, it can be shown that

$$f(X_i,Y_j)=\begin{cases}
f(X_{i-1},Y_j) &amp; \text{if } x_i\ne y_j,i &gt; 1\\
0 &amp; \text{if } x_i\ne y_j, i=1\\
f(X_{i-1},Y_j)+f(X_{i-1},Y_{j-1}) &amp; \text{if } x_i=y_j,j &gt; 1\\
\sum_{k=1}^i [x_k = y_j] &amp; \text{if }j=1
\end{cases}$$

That is, if the subsequence is 1 character long, count how many there are in the master sequence. If \$x_i=y_j\$, add the number of times the subsequence \$Y_{j-1}\$ occurred previously in \$X_{i-1}\$, as that is the number of times you can find this subsequence using this specific position \$x_i\$. Otherwise, ignore the character and only look at the sequence before \$x_i\$, that is, \$X_{i-1}\$.

With that, we write our code.

def submap master, sub
  # Minor optimization: Map the characters to indices. This way, we don't have
  # to go through the subsequence every time, which gives the best case scenario
  # a complexity of O(n+m) if all characters in Y are unique.
  subIndex = Hash.new{ |hash, key| hash[key] = [] } 
                                        # Initialize hash with default value []
  sub.chars.map.with_index do |c, i|    # For each character in Y
    subIndex[c] &lt;&lt; i                    # Add the index to the hash for that char.
  end

  subCount = [0] * sub.length           # Initialize the previous results f(X, Y_j).

  master.chars do |c|                   # For each character in X
    indices = subIndex[c]               # Look up the indices for that character
    indices.reverse_each do |i|         # For each index (in reverse order)
      subCount[i] += i &gt; 0 ? subCount[i-1] : 1
                                        # Increment f(X, Y_j) by f(X, Y_{j-1}).
    end
  end
  return subCount[-1]                   # Return f(X, Y_m).
end