题解 | #查找两个字符串a,b中的最长公共子串#

//https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506?tpId=37&rp=1&ru=%2Fexam%2Foj%2Fta&qru=%2Fexam%2Foj%2Fta&sourceUrl=%2Fexam%2Foj%2Fta%3Fpage%3D1%26pageSize%3D50%26search%3D48%26tpId%3D37%26type%3D37&difficulty=&judgeStatus=&tags=&title=65&gioEnter=menu

#include <iostream>
#include <string.h>

using namespace std;

int main() {
    string s1, s2;

    while(cin >> s1 >>s2){
        if(s1.size()<s2.size())
            swap(s1, s2);

        int n = s1.size();
        int m = s2.size();
        int dp[m][n];
        int maxn = 0;

        memset(dp, 0, sizeof(dp));

        for(int i = 0;i<m;i++)
            for(int j = 0;j<n;j++){
                if(s2[i]==s1[j]){
                    if(i==0||j==0)
                        dp[i][j] = 1;
                    else
                        dp[i][j] = 1+dp[i-1][j-1];
                    maxn = max(maxn, dp[i][j]);
                }
        }

        for(int i = 0;i<m;i++)
            for(int j = 0;j<n;j++){
                if(dp[i][j]==maxn){
                    cout << s2.substr(i-maxn+1, maxn);
                    return 0;
                }
            }

    }
}