题目：
有两个字符串，求这两个字符串的最长公共子序列，所谓公共子序列是指
下标依次递增的字符串，如 abcdefsg kbcdssssfsg 的最长公共子序列为
bcdgsg,字符串的长度范围为 [1，100]

输入：
多个实例，每个实例两行，每行一个字符串
输出：
形式为 Case x:zzz ,x表示实例序号，从1开始，zzz 表示最长公共子序列
每个实例的输出占一行。

如：
输入：
ab
ab
agbcdf
kkbdckd
abcdefsg
kbcdssssfsg

输出：
Case 1:ab
Case 2:bcf
Case 3:bcdfsg

// my code
#include <stdio.h>
#include <string.h>
char a[100],b[100],m[101][101]={0};
void putOut(int i, int j){
 if(i==0 || j==0)
  return;
 else if(m[i][j] == m[i-1][j-1]+1){
  putOut(i-1,j-1);
  putchar(a[i-1]);
 }
 else if(m[i][j] > m[i-1][j])
  putOut(i,j-1);
 else
  putOut(i-1,j);
}

int main(void){
 unsigned int  i,j,n=1;
 while(gets(a)!=NULL){
  gets(b);
  for(i=1; i<=strlen(a); i++)
   for(j=1; j<=strlen(b); j++){
    if(a[i-1] == b[j-1])
     m[i][j] = m[i-1][j-1]+1;
    else if(m[i-1][j] > m[i][j-1])
     m[i][j] = m[i-1][j];
    else
     m[i][j] = m[i][j-1];
   }
  printf("Case %u:",n++);
  putOut(strlen(a),strlen(b));
  putchar('\n');
 }
 return 0;
}

评论