BM66. [最长公共子串]
https://www.nowcoder.com/exam/oj?tab=%E7%AE%97%E6%B3%95%E7%AF%87&topicId=295
BM66. 最长公共子串
题目的主要信息：
- 查找两个字符串str1，str2中的最长的公共子串
- 保证str1和str2的最长公共子串存在且唯一
- 进阶要求：时间复杂度：
，空间复杂度：
方法一：暴力枚举
具体做法：
遍历str1每个字符作为起点，然后遍历以其为起点的每个长度的长度，即暴力枚举字符串str1的所有子串，用find函数查看每个子串是否在字符串str2中出现，如果出现比较长更新为较长的子串长度。
class Solution {
public:
string LCS(string str1, string str2) {
string res = "";
for(int i = 0; i < str1.length(); i++){ //遍历sre1每个起始点的每个长度
for(int j = i; j < str1.length(); j++){
if(int(str2.find(str1.substr(i, j - i + 1))) < 0) //截取子串能够在str2中被找到
break;
else if(res.length() < j - i + 1) //更新较长的子串
res = str1.substr(i, j - i + 1);
}
}
return res;
}
};
复杂度分析：
- 时间复杂度：
，其中
是str1的长度，
是str2的长度，枚举str1所有的子串需要
，find函数查找str2中是否含有子串需要
- 空间复杂度：
，res属于返回必要空间
方法二：枚举改进 - 具体做法：*
其实找子串不用像方法一一样完全枚举，我们完全可以遍历两个字符串的所有字符串作为起始，然后同时开始检查字符是否相等，相等则不断后移，增加子串长度，如果不等说明以这两个为起点的子串截止了，不会再有了，后续比较长度维护最大值即可。
class Solution {
public:
string LCS(string str1, string str2) {
int length = 0;
string res = "";
for(int i = 0; i < str1.length(); i++){ //遍历s1每个起始点
for(int j = 0; j < str2.length(); j++){ //遍历s2每个起点
int temp = 0;
string temps = "";
int x = i, y = j;
while(x < str1.length() && y < str2.length() && str1[x] == str2[y]){ //比较每个起点为始的子串
temps += str1[x];
x++;
y++;
temp++;
}
if(length < temp){ //更新更大的长度子串
length = temp;
res = temps;
}
}
}
return res;
}
};
复杂度分析：
- 时间复杂度：
，其中
- 空间复杂度：
，res属于返回必要空间，temps属于临时空间，最坏情况下长度为
方法三：动态规划
具体做法：
动态规划继承自方法二，我们可以用表示在str1中以第
个字符结尾在str2中以第
个字符结尾时的公共子串长度，遍历两个字符串填充dp数组，在这个过程中比较维护最大值即可。
转移方程为：如果遍历到的该位两个字符相等，则此时长度等于两个前一位长度+1，，如果遍历到该位时两个字符不相等，则置为0，因为这是子串，必须连续相等，断开要重新开始。
每次更新后，我们维护最大值,并更新该子串结束位置，最后根据最大值结束位置即可截取出子串。
class Solution {
public:
string LCS(string str1, string str2) {
vector<vector<int> > dp(str1.length() + 1, vector<int>(str2.length() + 1, 0)); //dp[i][j]表示到str1第i个个到str2第j个为止的公共子串长度
int max = 0;
int pos = 0;
for(int i = 1; i <= str1.length(); i++){
for(int j = 1; j <= str2.length(); j++){
if(str1[i - 1] == str2[j - 1]){ //如果该两位相同
dp[i][j] = dp[i - 1][j - 1] + 1; //则增加长度
}
else{ //否则
dp[i][j] = 0; //该位置为0
}
if(dp[i][j] > max){ //更新最大长度
max = dp[i][j];
pos = i - 1;
}
}
}
return str1.substr(pos - max + 1, max);
}
};
复杂度分析：
- 时间复杂度：
，其中
- 空间复杂度：
