Problem K
Subsequences in Substrings
You are given two strings $s$, and $t$. Count the number of substrings of $s$ that contain $t$ as a subsequence at least once.
Note that a $substring$ and a $subsequence$ both consist of characters from the original string, in order. In a $substring$, the characters must be contiguous in the original string, but in a $subsequence$, they are not required to be contiguous. In the string abcde, ace is a subsequence but not a substring.
If $s$ is aa and $t$ is a, then the answer is $3$: [a]a, [aa], and a[a].
Input
Each test case will consist of exactly two lines.
The first line will contain string $s$ ($1\! \le \! |s|\! \le \! 10^5, s\! \in \! [a{-}z]^*$), with no other characters.
The second line will contain string $t$ ($1\! \le \! |t|\! \le \! 100, |t|\! \le \! |s|, t\! \in \! [a{-}z]^*$), with no other characters.
Output
Output a single integer, which is the number of substrings of $s$ that contain $t$ as a subsequence at least once.
| Sample Input 1 | Sample Output 1 |
|---|---|
abcdefghijklmnopqrstuvwxyz a |
26 |
| Sample Input 2 | Sample Output 2 |
|---|---|
abcdefghijklmnopqrstuvwxyz m |
182 |
| Sample Input 3 | Sample Output 3 |
|---|---|
penpineappleapplepen ppap |
68 |
