题解 | #Coincidence#

#include <iostream>
using namespace std;

//最长公共子序列
int dp[100][100];
int longest(string s1,string s2){
    int ans=0;
    
    int n1=s1.size();
    int n2=s2.size();
    for(int i=-1;i<n1;i++){
        for(int j=-1;j<n2;j++){
            if(i==-1||j==-1)
                dp[i+1][j+1]=0;
            else if(s1[i]==s2[j])
                dp[i+1][j+1]=dp[i][j]+1;
            else
                dp[i+1][j+1]=max(dp[i][j+1],dp[i+1][j]);
            ans=max(ans,dp[i+1][j+1]);
        }
    }
    return ans;
}

int main(){
    string str1,str2;
    cin>>str1>>str2;
    int ans=longest(str1,str2);
    cout<<ans<<endl;
    return 0;
}