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

#include <iostream>
#include <string>
#include <algorithm>
#include<vector>
using namespace std;
string getLongestStr(string str1, string str2)
{
	int n, m;
	string result, lowStr, longStr;
	if (str1.size() > str2.size()) {
		lowStr = str2;
		longStr = str1;
	}
	else {
		lowStr = str1;
		longStr = str2;
	}
	n = longStr.size() + 1;
	m = lowStr.size() + 1;
	int max = 0;
	vector<vector<int>> dp(m, vector<int>(n));
	for (int i = 1; i < m; i++) { // 先遍历较短的字符串
		for (int j = 1; j < n; j++) {// 再遍历较长的字符串
			if (longStr[j - 1] == lowStr[i - 1]) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				if (dp[i][j] > max) {
					max = dp[i][j];
					result = lowStr.substr(i - max, max);
				}
			}
		}
	}
	return result;
}
int main(){
    string str1, str2;
	cin >> str1 >> str2;
	vector<string> s;
    cout << getLongestStr(str1, str2) << endl;
	return 0;
}