题解 | 动态规划+预处理

#include <iostream>
#include <string>
#include <cstring>

using namespace std;

#define fas(i,a,b) for(int i=a;i<b;++i) //[)


int matrix[301][301];
int main() 
{
    string str1,str2;
    while (cin >> str1>>str2) 
    { // 注意 while 处理多个 case
        memset(matrix,0, sizeof(int)*(301*301));
        if(str2.size()<str1.size())
        {
            string tmp;
            tmp=str1;
            str1=str2;
            str2=tmp;
        }
        str1="0"+str1;
        str2="0"+str2;
        int keepi,maxv=0;
        fas(i,1,str1.size())
        {
            fas(j,1,str2.size())
            {
                if(str1[i]==str2[j])
                    matrix[i][j]=matrix[i-1][j-1]+1;
                // else
                // {
                //     matrix[i][j]=max(matrix[i][j-1],matrix[i-1][j]);
                // }
                if(maxv<matrix[i][j])
                {
                    maxv=matrix[i][j];
                    keepi=i;
                }
            }
        }
        // fas(i,1,str1.size())
        // {
        //     fas(j,1,str2.size())
        //         cout<<matrix[i][j]<<" ";
        //     cout<<endl;
        // }


        for(int i=keepi-(maxv-1);i<=keepi;++i)
        {
            cout<<str1[i];
        }
        cout<<endl;
    }
}
// 64 位输出请用 printf("%lld")