题解 | #公共子串计算#动态规划

#include <iostream>
#include <vector>
#include<cstring>
using namespace std;
int main()
{
    string s1 , s2 ;
    getline(cin , s1) ;
    getline(cin , s2) ;
    vector<vector<int>> dp(s2.size() , vector<int>(s1.size())) ;
    int size1 = s1.size() ;
    int size2 = s2.size() ;
    int max = 0 ;
    
    for(int i = 0 ; i < size2 ; i++)
    {
        if(s2[i] == s1[0])
        {
            dp[i][0] = 1 ;
            max = 1 ;
        }
    }
    for(int j = 0 ; j < size1 ; j++)
        if(s1[j] == s2[0])
        {
            dp[0][j] = 1 ;
            max = 1 ;
        }
    for(int i = 1 ; i < size2 ; i++)
        for(int j = 1 ; j < size1 ; j++)
        {
            if(s1[j] == s2[i])
            {
                dp[i][j] = dp[i - 1][j - 1] + 1 ;
                 if(dp[i][j] > max)
                     max = dp[i][j] ;
            }
        }
    cout << max << endl ;
    return 0;
}