题目：有两个字符串，求这两个字符串的最长公共子序列，所谓公共子序列是指下标依次递增的字符串，如 abcdefsg kbcdssssfsg 的最长公共子序列为bcdgsg,字符串的长度范围为 [1，100] 输入：多个实例，每个实例两行，每行一个字符串输出：形式为 Case x:zzz ,x表示实例序号，从1开始，zzz 表示最长公共子序列每个实例的输出占一行。 如：输入：ababagbcdfkkbdckdabcdefsgkbcdssssfsg 输出：Case 1:abCase 2:bcfCase 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;}

评论