当前位置:网站首页>[POJ 2250] complexity (longest common subsequence LCS)

[POJ 2250] complexity (longest common subsequence LCS)

2021-07-28 14:52:59 mb60f8ef05632b9

subject
A string of LCS, I don't know the output solution ,dp Record where it was transferred from , After that, you need to transfer back step by step, save the solution, and then output .

#include<cstdio>
#include<cstring>
#define N 102
#define M 32
int n,m,dp[N][N],ans[N][N];
char s1[N][M],s2[N][M],str[N][M];
void solve(){
    memset(dp,0,sizeof dp);
    memset(ans,0,sizeof ans);
    int i,j,t,ti;
    for (i=1;i<=n;i++)
        for (j=1;j<=m;j++)
            if (strcmp(s1[i-1],s2[j-1])==0)
                dp[i][j]=dp[i-1][j-1]+1;
            else if(dp[i-1][j]>dp[i][j-1]){
                dp[i][j]=dp[i-1][j];
                ans[i][j]=1;// from s1 Transfer to 
            }else
                dp[i][j]=dp[i][j-1];
    i=n,j=m;
    t=dp[n][m];
    while(i&&j)
        if(strcmp(s1[i-1],s2[j-1])==0){
            memcpy(str[--t],s1[i-1],sizeof s1[i-1]);
            i--;j--;
        }
        else{
            ti=i;
            i-=ans[i][j];
            j-=1^ans[ti][j];//ans=0 It is s2 Transferred , so j--
        }
    for(i=0;i<dp[n][m];i++) printf("%s ",str[i]);
    printf("\n");
}
int main(){
    while (~scanf("%s",&s1[n]))
        if (s1[n][0]=='#'){
            while (scanf("%s",&s2[m])&&s2[m][0]!='#') m++;
            solve();
            n=m=0;
        }
        else n++;
    return 0;
}
  

 


┆ cool ┆ warm ┆ drop ┆ etc. ┆ Her love ┆ I ┆ I ┆ in ┆ take ┆ ┆ can ┆ Yes ┆ Modest ┆ Killing ┆ that ┆ ┆ Big ┆ beginning ┆ ┆ however ┆
┆ thin ┆ One ┆ In the ┆ you ┆ Of ┆ also ┆ no ┆ ┆ Come on ┆ ┆ yes ┆ Come on ┆ Inferior ┆ no ┆ some ┆ ┆ Wild goose ┆ end ┆ ┆ and ┆
┆ ┆ warm ┆ ┆ Such as ┆ The earth ┆ standing ┆ Yes ┆ ┆ also ┆ ┆ I ┆ ┆ Of ┆ Yes ┆ fine ┆ ┆ also ┆ no ┆ ┆ you ┆
┆ ┆ this ┆ ┆ try ┆ Fang ┆ stay ┆ flee ┆ ┆ Meeting ┆ ┆ stay ┆ ┆ clear ┆ Come on ┆ accurate ┆ ┆ no ┆ Yes ┆ ┆ no ┆
┆ ┆ raw ┆ ┆ explore ┆ ┆ most ┆ avoid ┆ ┆ stay ┆ ┆ this ┆ ┆ morning ┆ ┆ Of ┆ ┆ Yes ┆ Come on ┆ ┆ Yes ┆
┆ ┆ And ┆ ┆ like ┆ ┆ No ┆ ┆ ┆ this ┆ ┆ in ┆ ┆ no ┆ ┆ kill ┆ ┆ Come on ┆ ┆ ┆ Come on ┆

版权声明
本文为[mb60f8ef05632b9]所创,转载请带上原文链接,感谢
https://chowdera.com/2021/07/20210722135259058j.html