506. Subsequences Of Substrings

Time limit per test: 0.5 second(s)
Memory limit: 262144 kilobytes
input: standard
output: standard

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 it. 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.
Input
The first line of the input file contains the text — a non-empty string of lowercase English letters, no more than letters long. 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
Output one integer — the sought number of ways.
Example(s)
sample input
sample output
abraaadabraa
baa
23


Online Contester Team © 2002 - 2010. All rights reserved.