题解 | #公共子串计算#

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

int main() {
    string str_a, str_b;
    cin >> str_a >> str_b;
    const int len_a = str_a.size();
    const int len_b = str_b.size();

    int max_len = 0;
    vector<int> dp(len_b);
    for (int i = 0; i < len_b; i++) {
        if (str_a[0] == str_b[i]) dp[i] = 1;
    }
    for (int i = 1; i < len_a; i++) {
        for (int j = len_b - 1; j >= 0; j--) {
            if (j == 0) {
                if (str_b[0] == str_a[i]) dp[0] = 1; 
            }
            else if (str_b[j] == str_a[i]) {
                dp[j] = dp[j - 1] + 1;
            }
            else {
                dp[j] = 0;
            }
            max_len = max(max_len, dp[j]);
        }
    }

    cout << max_len;
}
// 64 位输出请用 printf("%lld")

dp矩阵改一下就可以满足空间要求了