- Prepare
- Algorithms
- Dynamic Programming
- LCS Returns

# 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 :

- 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.