QOJ.ac

QOJ

Time Limit: 3 s Memory Limit: 1024 MB
[-1]

# 3010. Subsequences in Substrings

Statistics

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 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|s|105,s[az]), with no other characters.

The second line will contain string t (1|t|100,|t||s|,t[az]), 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

Sample Output 1

26

Sample Input 2

abcdefghijklmnopqrstuvwxyz
m

Sample Output 2

182