Description
This winter is very cold, JYL wants to find a female companion to accompany him through this cold winter.
In order to meet more girls, he decided to use dating software.
However, JYL is deeply afraid that his handsomeness will attract too many girls.
Therefore, he decided to find the girl who had the most in common with him to develop a relationship with.
The selection method is as follows:
Given two strings (representing the information of JYL and that girl), please calculate the length of the longest common subsequence of the two strings.
Hint: You can use a 2D table to record the intermediate results.
Note:
A subsequence of a string is a new string generated from the original string with some characters (can be none) deleted without changing the relative order of the remaining characters.
For example, "ace" is a sequence of "abcde".
God bless him......
Input
There are two strings separated by a newline character.
Note that the length of the two strings are less than 3100.
Output
The length of the longest common sequence.
Note that you have to print '\n' in the end.