学步园

#include<stdio.h>
#include<string.h>
int max[101][101];
int flag1[101],flag2[101];
typedef struct
{
 int i;
 int j;
}point;

point sign[101][101];
char ch1[101],ch2[101];

void LCS_LENGH(int len1,int len2)
{
 int i,j;
 for(i=0;i<=len1;i++)//max,sign 的两边初始化
  sign[i][0].i=max[i][0]=0;
 for(j=0;j<=len2;j++)
  sign[0][j].j=max[0][j]=0;

 for(i=1;i<=len1;i++)//每一个进行配备
  for(j=1;j<=len2;j++)
  {
   if(ch1[i]==ch2[j])//行和列的字符匹配上 则进行标记
   {
    max[i][j]=max[i-1][j-1]+1; //斜上加1
    sign[i][j].i=i-1;          //路劲标记为为 斜上的坐标
    sign[i][j].j=j-1;
   }
   else if(max[i-1][j]>=max[i][j-1])
   {
    max[i][j]=max[i-1][j];
    sign[i][j].i=i-1;   //路劲标记为为 正左的坐标
    sign[i][j].j=j;
   }
   else
   {
    max[i][j]=max[i][j-1];
    sign[i][j].i=i;         //路劲标记为为 正上边的坐标
    sign[i][j].j=j-1;
   }
  }
}

void print(int len1,int len2)
{
 int i,j,tempi;
 
 for(i=1;i<=len1;i++)//输出max值
 {  
  flag1[i]=0;
  for(j=1;j<=len2;j++)
  {
   flag2[j]=0;
   printf("%d ",max[i][j]);
  }
  printf("\n");
 } 
 printf("\n");

 for(i=1;i<=len1;i++)//输出路劲
 {
  for(j=1;j<=len2;j++)
   printf("%d %d   ",sign[i][j].i,sign[i][j].j);
  printf("\n");
 }
 printf("\n");
 
 i=len1;
 j=len2;
 while(i!=0||j!=0)//max中最大LCS  路径寻踪
 {  
    if((i==sign[i][j].i+1)&&(j==sign[i][j].j+1))
  {
    flag1[i]=1;
    flag2[j]=1;
  }

  tempi=i;
  i=sign[i][j].i;
  
  j=sign[tempi][j].j;
 }

   printf("%s\n",ch1+1);
 for(i=1;i<=len1;i++)//标下标线
 {
  if(flag1[i]==0)
   printf(" ");
  else
   printf("_");
 }
 printf("\n");

 printf("%s\n",ch2+1);
 for(j=1;j<=len2;j++)
 {
  if(flag2[j]==0)
   printf(" ");
  else
   printf("_");
 }
 printf("\n");
}

int main()
{   freopen("1.txt","r",stdin);
 gets(ch1+1);
 gets(ch2+1);

 int len1,len2;
 len1=strlen(ch1+1);
 len2=strlen(ch2+1);

 LCS_LENGH(len1,len2);
    print(len1,len2);
 return 0;
}