Problem Statement Takahashi tried to type a string S consisting of lowercase English letters using a keyboard.
He was typing while looking only at the keyboard, not the screen.
Whenever he mistakenly typed a different lowercase English letter, he immediately pressed the backspace key. However, the backspace key was broken, so the mistakenly typed letter was not deleted, and the actual string typed was T.
He did not mistakenly press any keys other than those for lowercase English letters.
The characters in T that were not mistakenly typed are called correctly typed characters.
Count the number of subsequences in String T can form String S.
Constraints: S and T are strings of lowercase English letters with lengths between 1 and 2×(10)^5, inclusive.
Input: The input is given from Standard Input in the following format: S T
Output: Print number of subsequences of string T can form String S.
Sample Input 1: abc axbxyc
Sample Output 1: 1
Explaination: abc can form subsequence in (1,3 and 6) positions.
Sample Input 2: abac abacusabacus
Sample Output 2: 7
Explaination: abac can form subsequence in (1,2,3,4), (1,2,3,10),(1,2,7,10),(1,2,9,10),(1,8,9,10),(3,8,9,10) and (7,8,9,10) positions.
Sample Input 3: aaaaa aa
Sample Output 3: 0
What's the approach for this problem?
