506. Subsequences Of Substrings
Time limit per test: 0.5
Memory limit: 262144
Andrew has just made a breakthrough in steganography: he realized that one
can hide a message in a bigger text by making the message a subsequence
of the text.
We remind that a string s
is called a subsequence
of string t
if one can remove some (possibly none) letters from t
and obtain s
Andrew has prepared a text (represented by a string) with a hidden message
(represented by another string which is a subsequence of the first string).
But it turns out that he doesn't have enough space to write the text, so he
wonders if he can remove some letters from the beginning and/or the end
of his text in such a way that the hidden message still stays a subsequence of
You should find out how many ways are there to remove some (possibly none)
letters from the beginning of the given text and some (possibly none)
letters from the end of the given text in such a way that the given message
is a subsequence of the remaining string. Two ways are distinct if the number
of letters removed from the beginning or from the end or both are distinct, even
if the resulting string is the same.
The first line of the input file contains the text — a non-empty string
of lowercase English letters, no more than
The second line of the input file contains the message — a non-empty string
of lowercase English letters, no more than 100 letters long.
It is guaranteed that the message is a subsequence of the given text.
Output one integer — the sought number of ways.