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.
The first line contains a single string denoting .
The second line contains a single string denoting .
- 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).
- for of the maximum score.
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.
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 subsequence
aaa(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 of
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.