We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
  1. Prepare
  2. Algorithms
  3. Dynamic Programming
  4. LCS Returns

LCS Returns

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 :

  1. 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).
  2. 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.