Given two strings, and , find and print the total number of ways to insert a character at any position in string such that the length of the Longest Common Subsequence of characters in the two strings increases by one.
Input Format
The first line contains a single string denoting .
The second line contains a single string denoting .
Constraints
Scoring
- Strings and are alphanumeric (i.e., consisting of arabic digits and/or upper and lower case English letters).
- The new character being inserted must also be alphanumeric (i.e., a digit or upper/lower case English letter).
Subtask
- for of the maximum score.
Output Format
Print a single integer denoting the total number of ways to insert a character into string in such a way that the length of the longest common subsequence of and increases by one.
Sample Input
aa
baaa
Sample Output
4
Explanation
The longest common subsequence shared by and is aa, which has a length of . There are two ways that the length of the longest common subsequence can be increased to by adding a single character to :
- There are different positions in string where we could insert an additional
ato create longest common subsequenceaaa(i.e., at the beginning, middle, and end of the string). - We can insert a
bat the beginning of the string for a new longest common subsequence ofbaa.
As we have ways to insert an alphanumeric character into and increase the length of the longest common subsequence by one, we print on a new line.