Counting Embeddings — Solution & Editorial

Back to the Problem

dp[j] = embeddings of T's first j characters; for each character of S, update j downward: on a match dp[j] += dp[j−1]. The empty prefix has one embedding.

Complexity: O(|S|·|T|)

Watch out: Update j from high to low, or each text character can be reused within one step.