Distinct Subsequences
mediumDynamic Programming II+20 XPTime limit 2s
Count how many times the word t appears in the text s as a subsequence: choose positions in s (in increasing order) whose letters spell t. Two ways are different if they use a different set of positions. Print the count modulo 1 000 000 007.
Input: two lines: s, then t.
Output: the number of ways modulo 10⁹ + 7.
Constraints: 1 ≤ length of s, t ≤ 1000; lowercase letters.
Example: t = bag appears in s = babgbag in 5 ways.
Think about it: ways[i][j] = ways to form the first j letters of t from the first i letters of s. The letter s[i] is either skipped (ways[i−1][j]) or, when it equals t[j], used (+ ways[i−1][j−1]). One row is enough if you update j from right to left.
Sample input 1
babgbag bag
Sample output 1
5
Sample input 2
rabbbit rabbit
Sample output 2
3
Read input from standard input and print the answer to standard output. Your code runs in a secure sandbox against the samples (Run) and hidden tests (Submit).