| Description |
| 给定两个字符串，输出他们的最长公共子序列，要求字典序最小。 |
| Input |
| 有多组数据，每组数据包含两行，每行一个字符串，每个字符串的长度不超过1000。 每个字符串仅包含小写字母。 |
| Output |
| 对于每组数据，输出一行，字典序最小的公共子序列。 |
| Sample Input |
| abcdefghaaa abcdefghbbb oxuhi ehozu oxuhijednr ehozujudgz |
| Sample Output |
| abcdefgh ou oujd |
思路:和上一道题很像，但是再求最长公共子序列的时候应该倒着求，从最小字符'a'枚举但是在枚举时是从最后一个开始的所以就逆序过来操作。
代码如下：
#include#include #include #include #include #include using namespace std;int dp[1002][1002];char ch1[1002], ch2[1002], temp[1002];int last1[1002][27], last2[1002][27]; int len1, len2, flag; void find(int x, int y, int len){ int i, j; if(flag) return ; if(len<=0) { flag=1; for(i=dp[len1][len2]; i>=1; i--) printf("%c", temp[i]); printf("\n"); return ; } if(x>0&&y>0) { for(i=0; i<26; i++) { int t1=last1[x][i]; int t2=last2[y][i]; if(dp[t1][t2]==len) { temp[len]='a'+i; find(t1-1, t2-1, len-1); } } }} int main(){ int i, j; char c; while(scanf("%s %s", &ch1[1], &ch2[1])!=EOF) { len1=strlen(&ch1[1]); len2=strlen(&ch2[1]); for(i=1; i<=len1/2; i++) { c=ch1[i], ch1[i]=ch1[len1-i+1], ch1[len1-i+1]=c; } for(i=1; i<=len2/2; i++) { c=ch2[i], ch2[i]=ch2[len2-i+1], ch2[len2-i+1]=c; } for(i=0;i<=len1;i++) dp[i][0]=0; for(i=0;i<=len2;i++) dp[0][i]=0; for(j=0;j<26;j++) for(i=0;i<=len1;i++) last1[i][j]=0; for(j=0;j<26;j++) for(i=0;i<=len2;i++) last2[i][j]=0; for(i=1; i<=len1; i++) for(j=1; j<=len2; j++) { if(ch1[i]==ch2[j]) dp[i][j]=dp[i-1][j-1]+1; else dp[i][j]=max(dp[i][j-1], dp[i-1][j]); } for(i=1; i<=len1; i++) for(j=0; j<26; j++) { if(ch1[i]=='a'+j) last1[i][j]=i; else last1[i][j]=last1[i-1][j]; } for(i=1; i<=len2; i++) for(j=0; j<26; j++) { if(ch2[i]=='a'+j) last2[i][j]=i; else last2[i][j]=last2[i-1][j]; } memset(temp, 0, sizeof(temp)); temp[dp[len1][len2]+1]='\0'; flag=0; find(len1, len2, dp[len1][len2]); } return 0;}