题解 | #最长公共子串#
最长公共子串
https://www.nowcoder.com/practice/f33f5adc55f444baa0e0ca87ad8a6aac
2022.0815算法第26题最长公共子串
这个和最长公共子序列采用的方法是一样的，需要构造状态矩阵，记录当前的子串状态。
主要在于获取最长子串的位置，用于分割子串。
可以记录最长子串的长度和最长子串出现的最后的索引位置。
这点需要使用两个变量
int maxLength=0,end=0;然后获取状态矩阵
for(int i=1;i<=str1.size();i++){
for(int j=1;j<=str2.size();j++){
if(str1[i-1]==str2[j-1]){
dp[i][j]=dp[i-1][j-1]+1;
if(dp[i][j]>maxLength){
maxLength=dp[i][j];
end=i-1;
}
}
else{
dp[i][j]=0;
}
}
}
其中，状态转移方程为
dp[i][j]=dp[i-1][j-1]+1;之后就是对状态方程进行处理，获取相应的变量。
最后根据最长子串的长度和结束位置分割子串。
return str1.substr(end-maxLength+1,maxLength);状态方程不好想，而且需要记录两个变量。
下标也不能出错。
投递美团等公司10个岗位
百威成长空间 51人发布