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

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

int main() {
    string s,t;
    cin >> t >> s;
    if(s.size() > t.size()) {
        swap(s,t);
    }
    vector<vector<int>> dq(s.size() + 1,vector<int>(t.size()+1));
    int lMax = 0;
    int maxEnd = 0;
    for(auto i = 1; i <= s.size(); i++) {
        for(auto j = 1; j <= t.size(); j++) {
            auto& cur = dq[i][j];
            auto& pre = dq[i-1][j-1];
            if(s[i-1] == t[j-1]) {
                cur = pre + 1;
                if(cur > lMax) {
                    lMax = cur;
                    maxEnd = i-1;
                }
            } else {
                cur = 0;
            }
        }
    }
    cout << s.substr(maxEnd - lMax+1, lMax) << endl;
}
// 64 位输出请用 printf("%lld")