LCS

#include <bits/stdc++.h>
#include <iostream>
#define pb push_back
#define INF 1000000000
#define mp make_pair
#define ll long long
#define tc int t; cin>>t; while(t--)
#define for0(i,n) for(int i=0; i<n; i++)
#define for1(i,n) for(int i=1; i<=n; i++)
#define pi pair<int,int>
#define pii vector<pair<int,int>>

using namespace std;

int solve(int i, int j, string s1, string s2, vector<vector<int>> &dp) {
    //base case
    if (i >= s1.size() || j >= s2.size()) return 0;

    //memorization
    if (dp[i][j] != -1) return dp[i][j];

    //if character matches
    if (s1[i] == s2[j]) return 1 + solve(i + 1, j + 1, s1, s2, dp);

    else {
        int left = solve(i, j + 1, s1, s2, dp);
        int right = solve(i + 1, j, s1, s2, dp);
        return dp[i][j] = max(left, right);
    }
}

int main() {
    init();
    // tc
    {
        string s1, s2;
        cin >> s1 >> s2;

        int n = s1.size();
        int m = s2.size();

        vector<vector<int>> dp(n, vector<int> (m, -1));
        cout << solve(0, 0, s1, s2, dp);

    }

    return 0;
}