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]**.

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 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 |