시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 512 MB 8 7 7 87.500%

문제

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 ≤ |s| ≤ 105, s∈[a−z]*), with no other characters. The second line will contain string t (1 ≤ |t| ≤ 100, |t| ≤ |s|, t∈[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.

예제 입력 1

abcdefghijklmnopqrstuvwxyz
a

예제 출력 1

26

예제 입력 2

abcdefghijklmnopqrstuvwxyz
m

예제 출력 2

182

예제 입력 3

penpineappleapplepen
ppap

예제 출력 3

68