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 a to create longest common subsequence aaa (i.e., at the beginning, middle, and end of the string).
We can insert a b at the beginning of the string for a new longest common subsequence of baa.
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.