lcs(continue).cpp

LCS,即最常公共子序列的的C语言解法。prepare_for_backdate(char

/*算法：lcs算法并输出最长公共子序列
 *
 *主要函数：prepare_for_backdate(char，char，int，int)，lcs(char，int，int)
 *          第一个函数是为后面的回溯法求得最长公共子序列做准备，并可得到子序列长度。第二个函数是输出子序列的。并用到了第一个
 *          函数的结果。因为要得到最终的子序列，要知道那些地方是可输出的位置，因此构造数组b[][]，当为1时表明当前位置匹配，可
 *          输出，为2时需要往上回溯，为3时需要往左回溯，直到找到下一个为1的位置。而c[][]数组是保存找子序列过程中匹配位数。
 *
 *待改进的地方：还不能将两个序列的所有最长公共子序列全部输出
 *
 *说明：1.由于Visual C++ 2005 Express不支持动态数组，所以只好用30*30的数组表示一些必要的参数；
 *      2.输入的字符串长度不可超过30.*/
#include<stdafx.h>
#include<stdio.h>
#include<string.h>
#define N 30
#define M 30
int c[N][M],b[N][M];
int prepare_for_backdate(char x[],char y[],int n,int m)
{  int i,j=0;
 for(i=0;i<=n;i++)
   c[i][0]=0;
 for(j=0;j<=m;j++)
   c[0][j]=0;
 for(i=1;i<=n;i++)//分三种情况讨论
   for(j=1;j<=m;j++)
   {
	   if(x[i-1]==y[j-1])                  // i-1  *
	                                   //  *   i
       { 
	       c[i][j]=c[i-1][j-1]+1;
           b[i][j]=1;
       }
       else//如果两位不相等         //    *     i
	                                // i-1或i   i
       { 
	       if(c[i-1][j]>=c[i][j-1])
           {  
		       c[i][j]=c[i-1][j];
               b[i][j]=2;
           }
           else                          //  *   i-1
		                                 //  i    i
           {
		       c[i][j]=c[i][j-1];
               b[i][j]=3;
           }
	   }
   }
  printf("The result is :%d\n",c[n][m]);
  printf("\nThe result of c[i][j] is :\n\t\t");
  for(i=0;i<=n;i++)
  {  
	   for(j=0;j<=m;j++)
          printf("%3d",c[i][j]);
   printf("\n\t\t");
  }
  printf("\nThe result of b[i][j] is :\n\t\t");
    for(i=0;i<=n;i++)
  {  
	   for(j=0;j<=m;j++)
          printf("%3d",b[i][j]);
   printf("\n\t\t");
  }
  return 0;
  }
void lcs(char x[],int i,int j)
{
    if(i==0||j==0)
        return;
    if(b[i][j]==1)       //往左上角找
    {   
	    lcs(x,i-1,j-1);
	    putchar(x[i-1]);//printf("%c",x[i-1]);
    }
    else 
	    if(b[i][j]==2)//往上找
           lcs(x,i-1,j);
        else         //往左找
		   if(b[i][j]==3)
               lcs(x,i,j-1);
}
int main()
{
	int length_a,length_b;
	char a[N],b[N];
	printf("Please input two strings a,b:\n");
	gets(a);
	gets(b);
	length_a=(int)strlen(a);
	length_b=(int)strlen(b);
	prepare_for_backdate(a,b,length_a,length_b);
	printf("\nThe longest subsequence is:");
    lcs(a,length_a,length_b);
}