本文主要是介绍FZU - 2024 LCS EditStep，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：给定a，b两个字符串，长度Len(1 <=Len<=1000)，分别求出这两个字符串的LCS长度和EditStep。其中：
LCS为两个字符串的最长公共子串。
EditStep为，通过增加一个字符，或者删除一个字符，或者替换一个字符使得a串与b串相同需要的操作个数。
思路：LCS就不说了，EditStep就是：ans[i][j]表示str1的前i,str2的前j的最少步数，三种情况，删除，添加，替换，删除和替换的效果是一样的，如果str1[i]==str2[j]的话，那么就是dp[i-1][j-1]，不等的话，如果替换的话就是在这个的基础上再+1，取所有情况的最小值
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int MAXN = 1005;char str1[MAXN],str2[MAXN];
int dp[MAXN][MAXN];
int ans[MAXN][MAXN];int main(){int t,cas=1;scanf("%d%*c",&t);while (t--){scanf("%s%s",str1,str2);memset(dp,0,sizeof(dp));int len1 = strlen(str1),len2 = strlen(str2);for (int i = 0; i <= len1; i++)ans[i][0] = i;for (int j = 0; j <= len2; j++)ans[0][j] = j;int t;for (int i = 1; i <= len1; i++)for (int j = 1; j <= len2; j++){if (str1[i-1] == str2[j-1]){dp[i][j] = dp[i-1][j-1] + 1;t = 0;}else {dp[i][j] = max(dp[i-1][j],dp[i][j-1]);t = 1;}ans[i][j] = min(ans[i-1][j-1]+t,min(ans[i-1][j]+1,ans[i][j-1]+1));}printf("Case %d: LCS=%d EditStep=%d\n",cas++,dp[len1][len2],ans[len1][len2]);}return 0;
}
这篇关于FZU - 2024 LCS EditStep的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
