题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
本题是利用动态规划的经典题目。首先需要注意的是，公共子串和公共子序列的区别，子串要求是连续的，而子序列不要求是连续的，要求的是相对位置不能错。
由于是连续的，所以我们以较短的字符串为基准（外循环），依次判断各个字符和较长的字符串的各个字符是否相等，如果相等则将dp数组的对应位置表示为dp[i-1][j-1]+1，否则为0。
同时不断更新和比较最大值（对角线上的最大值），并记录公共子序列的右端位置下标。
#include <iostream>
#include <string>
#include <vector>
using namespace std;
int main(){
string s1, s2;
getline(cin, s1, '\n');
getline(cin, s2, '\n');
int max = 0;
int end = 0;
int flag = 0;
if (s1.size() <= s2.size()) flag = 1;
string s11, s22;
// 以较短的那个字符串作为判断的基准
if (flag) {
s11 = s1;
s22 = s2;
} else {
s11 = s2;
s22 = s1;
}
vector<vector<int>> dp(s11.size() + 1, vector<int>(s22.size() + 1, 0));
for (int i = 1; i <= s11.size(); i++) {
for (int j = 1; j <= s22.size(); j++) {
if (s11[i - 1] == s22[j - 1]) {
dp[i][j] = dp[i - 1][j - 1] + 1;
if (dp[i][j] > max) {
max = dp[i][j];
end = i - 1;
}
} else {
dp[i][j] = 0;
}
}
}
string res;
res = s11.substr(end - (max - 1), max);
cout << res << endl;
return 0;
}
腾讯一面2190人在聊
查看3道真题和解析