lcslength.c

本算法实现的是对两个单字符串的扫描

#define M 100
#define N 100
char x[M+1],y[N+1];
int c[M+1][N+1];
lcslength(int m,int n)
{ int i,j;
  for(i=1;i<=m;i++) c[i][0]=0;
  for(i=1;i<=n;i++) c[0][i]=0;
  for(i=1;i<=m;i++)
   for(j=1;j<=n;j++)
     { if(x[i]==y[j])
         c[i][j]=c[i-1][j-1]+1;
       else
         if(c[i-1][j]>=c[i][j-1])
         c[i][j]=c[i-1][j];
         else c[i][j]=c[i][j-1];

      }
}/*lcslength*/
lcs(int i,int j)
{ if(i==0||j==0) return;
  if(c[i][j]==c[i-1][j-1]+1)
     { lcs(i-1,j-1);
       printf("%c",x[i]);
     }
  else if(c[i][j]==c[i-1][j])
     lcs(i-1,j);
  else lcs(i,j-1);
}/*lcs*/
main()
{ int i,j,m,n;
  char ch1,ch=0;
  printf("Please input one string x:\n");
  for(i=1;i<=M;i++)
    { scanf("%c",&ch);
      if(ch=='\n') break;
      x[i]=ch;
    }
    m=i-1;
    printf("%d\n",m);
  printf("Please input the other string y:\n");
  scanf("%c",&ch);
  for(i=1;i<=N;i++)
    { scanf("%c",&ch1);
      if(ch1=='\n') break;
      y[i]=ch1;
    }
    n=i-1;
    printf("%d\n",n);
  lcslength(m,n);
  printf("The length is:%d\n",c[m][n]);
  printf("The result:\n");
    lcs(m,n);
   getch();
}/*main lcslength*/