题目描述

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 \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 a single integer, which is the number of substrings of $s$ that contain $t$ as a subsequence at least once.

abcdefghijklmnopqrstuvwxyz
a

26

abcdefghijklmnopqrstuvwxyz
m

182

penpineappleapplepen
ppap

68