最长公共子序列（Longest Common Subsequence，LCS）又叫最长公共子串（不要求连续）。

其定义是：一个序列 S ，如果分别是两个或多个已知序列的子序列，且所有符合此条件序列中最长的，则 S 为已知序列的最长公共子序列。

【输入描述】

输入2行。第一行输入字符串 S1 ，第二行输入字符串 S2。

【输出描述】

输出1行。输出最长公共子序列的长度。

【输入样例】

123abc
abc123abc

【输出样例】

6

【参考程序】

//爱码岛编程
#include <bits/stdc++.h>
using namespace std;

string s1, s2;
int dp[1001][1001];

int main() {
    cin >> s1;
    cin >> s2;

    for (int i = 1; i <= s1.length(); i++)
        for (int j = 1; j <= s2.length(); j++) {
            if (s1[i] == s2[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]);
        }
        
    cout << dp[s1.length()][s2.length()] << endl;

    return 0;
}