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

#include <iostream>
#include <string>

using namespace std;

#define N 330
int dp[N][N];

string getLongestCommonString(string& a, string& b) {
    int lena = a.size() - 1;
    int lenb = b.size() - 1;
    int maxlen = 0;
    int maxidx = -1;
    for (int i = 1; i <= lena; ++i) {
        for (int j = 1; j <= lenb; ++j) {
            if (a[i] == b[j])    dp[i][j] = dp[i - 1][j - 1] + 1;
            if (dp[i][j] > maxlen) {
                maxlen = dp[i][j];
                maxidx = i;
            }
        }
    }
    return maxlen > 0 ? a.substr(maxidx - maxlen + 1, maxlen) : "";
}

int main() {
    string a, b;
    cin >> a >> b;
    a = " " + a;    // 实现输入的字符串从下标1开始
    b = " " + b;    // 实现输入的字符串从下标1开始
    if (a.length() > b.length()) swap(a, b); // 保证字符串长度a <= b
    cout << getLongestCommonString(a, b) << endl;

    return 0;
}