QOJ

Time Limit:3 s Memory Limit:1024 MB

#3010. Subsequences in Substrings

Problem Description

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 $\texttt{abcde}$, $\texttt{ace}$ is a subsequence but not a substring.

If $s$ is $\texttt{aa}$ and $t$ is $\texttt{a}$, then the answer is $3$: $\texttt{[a]a}$, $\texttt{[aa]}$, and $\texttt{a[a]}$.

Input

Each test case will consist of exactly two lines. The first line will contain string $s$ ($1 \leq |s| \leq 10^5, s \in [a-z]^*$), with no other characters.

The second line will contain string $t$ ($1 \leq |t| \leq 100, |t| \leq |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.

Samples

Sample Input 1

abcdefghijklmnopqrstuvwxyz
a

26

Sample Input 2

abcdefghijklmnopqrstuvwxyz
m

182