最长公共子序列和最长公共子串

xiaoxiao2021-02-28  130

#include<cstdio> #include<cstring> #define Max(x,y) x>y?x:y char a[1000],b[1000]; int dp[1000][1000]; int main() { while(scanf("%s%s",a,b)!=EOF){ //memset(dp,0,sizeof dp); int la=strlen(a); int lb=strlen(b); //printf("%d %d\n",la,lb); for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++){ if(i==0||j==0) dp[i][j]=0;//相当于初始化数组 else if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=Max(dp[i-1][j],dp[i][j-1]); } printf("%d\n",dp[la][lb]); } return 0; } for(int j=1;j<=lb;j++){ if(i==0||j==0) dp[i][j]=0; else if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=0; } int maxx=-1; for(int i=1;i<=la;i++) for(int j=1;j<=lb;j++) maxx=Max(maxx,dp[i][j]);
转载请注明原文地址: https://www.6miu.com/read-19648.html

最新回复(0)