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

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

int main() {
    string s, l;
    cin >> s >> l;
    if (s.size() > l.size()) swap(s, l);

    vector<vector<int>> dp(s.size() + 1, vector<int>(l.size() + 1, 0));
    int maxLen = 0;
    int pos;
    for (int i = 1; i <= s.size(); ++i) {
	  	//注意把短字符串循环放在外侧，这样可以先碰到短串靠前位置的公共子串
        for (int j = 1; j <= l.size(); ++j) {
            if (s[i - 1] == l[j - 1]) {
                dp[i][j] = dp[i - 1][j - 1] + 1;

            }
            else {
			  	// 可以不写，公共子串赋0，公共子序列为max(dp[i - 1][j], dp[i][j - 1])
                dp[i][j] = 0;
            }

            if (dp[i][j] > maxLen) {
                maxLen = dp[i][j];
                pos = i - 1;
            }
        }
    }

    if (maxLen) cout << s.substr(pos - maxLen + 1, maxLen) << endl;
    else cout << "" << endl;
}