/*算法：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);
}