题解 | #查找两个字符串a,b中的最长公共子串#
查找两个字符串a,b中的最长公共子串
https://www.nowcoder.com/practice/181a1a71c7574266ad07f9739f791506
和前面查找最长公共子串的长度其实是一样的，但是需要注意，题目中需要找到在较短字符串中出现第一次最长的公共子串，遍历的时候需要特别注意
#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;
}
投递云智研发公司等公司7个岗位
查看30道真题和解析