# [POJ 2250] complexity (longest common subsequence LCS)

2021-07-28 14:52:59

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 ┆

https://chowdera.com/2021/07/20210722135259058j.html