题目描述
算法课本上有最长子串的求解,本题加了一个限制,要求子串连续,我们只需要在原有动态规划的的算法基础上,将d[i][j]=max(d[i-1][j],d[i][j-1])删除,即可得到最长连续子串
时间复杂度$O(nm)$
C++ 代码
#include<iostream>
#include<cstring>
using namespace std;
int an[102][102];
int main(){
string x,y,res="";
cin>>x>>y;
int ml=0;
for(int i=1;i<=x.size();i++){
for(int j=1;j<=y.size();j++){
if(x[i-1]==y[j-1]){
an[i][j]=an[i-1][j-1]+1;
ml=max(ml,an[i][j]);
}
}
}
cout<<ml<<endl;
for(int i=y.size();i>0;i--){
for(int j=x.size();j>0;j--){
if(an[j][i]==ml){
cout<<x.substr(j-ml,ml);
return 0;
}
}
}
return 0;
}