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

#include<iostream>
#include<string>
#include<vector>
using namespace std;

int main(){
    string s1, s2;
    while(cin >> s1 >> s2){
        if(s1.length() > s2.length()) //使较小的字符串在前
            swap(s1, s2);
        vector<vector<int> > dp(s1.length() + 1, vector<int>(s2.length() + 1, 0)); //dp[i][j]表示到s1第i个个到s2第j个为止的公共子串长度
        int max = 0, end = 0;
        for(int i = 1; i <= s1.length(); i++){
            for(int j = 1; j <= s2.length(); j++){
                if(s1[i - 1] == s2[j - 1]) //如果该两位相同
                    dp[i][j] = dp[i - 1][j - 1] + 1; //则增加长度
                else //否则
                    dp[i][j] = 0; //该位置为0
                if(dp[i][j] > max){ //更新最大长度
                    max = dp[i][j];
                    end = i - 1;
                }
            }
        }
        cout << s1.substr(end - max + 1, max) << endl; //输出最长子串
    }
    return 0;
}