CF163A Substring and Subsequence

One day Polycarpus got hold of two non-empty strings $ s $ and $ t $ , consisting of lowercase Latin letters. Polycarpus is quite good with strings, so he immediately wondered, how many different pairs of " $ x $ $ y $ " are there, such that $ x $ is a substring of string $ s $ , $ y $ is a subsequence of string $ t $ , and the content of $ x $ and $ y $ is the same. Two pairs are considered different, if they contain different substrings of string $ s $ or different subsequences of string $ t $ . Read the whole statement to understand the definition of different substrings and subsequences. The length of string $ s $ is the number of characters in it. If we denote the length of the string $ s $ as $ |s| $ , we can write the string as $ s=s_{1}s_{2}...\ s_{|s|} $ . A substring of $ s $ is a non-empty string $ x=s[a...\ b]=s_{a}s_{a+1}...\ s_{b} $ ( $ 1

N/A

N/A

Let's write down all pairs " $ x $ $ y $ " that form the answer in the first sample: " $ s[1...1] $ $ t[1] $ ", " $ s[2...2] $ $ t[1] $ ", " $ s[1...1] $ $ t[2] $ "," $ s[2...2] $ $ t[2] $ ", " $ s[1...2] $ $ t[1 2] $ ".