文章
150
粉丝
0
获赞
558
访问
23.2k
#include<bits/stdc++.h>
using namespace std;
int dp[105][105];
int main(){
string a, b;
while(cin >> a >> b){
int la = a.size();
int lb = b.size();
// 初始化dp数组为0
memset(dp, 0, sizeof(dp));
int maxLen = 0; // 记录最长长度
int endPos = 0; // 记录最长子串在a中的结束位置(用于输出)
for(int i = 1; i <= la; ++i){
for(int j = 1; j <= lb; ++j){
// 当前字符相等,连续长度+1
if(a[i-1] == b[j-1]){
dp[i][j] = dp[i-1][j-1] + 1;
// 更新最大值(注意:取最后一个,所以>=)
if(dp[i][j] >= maxLen){
maxLen = dp[i][j];
endPos = i; // 记录在a中的结束位置
}
}
// 当前字符不相等,连续中断,长度为0
else{
dp[i][j] = 0;
}
}
} ...
登录后发布评论
暂无评论,来抢沙发