/*
content:最长公共子序列
方法：设A（a1....an-1）,B(b1.....bm-1);
       1）从后往前找，如果an-1 == bm-1那么 an-1 是子序列的最后一个元素。剩下的再A:(a1...an-2) B:(b1...bm-2)中继续找 
	   2）如果an-1 ！= bm-1 那么子序列一定在这两种情况下查找;
	       A:(a1...an-1) B:(b1...bm-2)      或     A:(a1...an-2) B:(b1...bm-1)
	    然后重复上面的方法。 
	    
	    查找子序列的长度的代码是从前往后遍历，确认子序列字符串的代码是重后往前遍历 
*/

#include <iostream>
#include <cstring>

using namespace std;

const static int N = 30; 

//求公共最长子序列的长度 
int lsclength(char *a,char *b, int c[][N])
{
	int m=strlen(a), n = strlen(b);
	int i,j;
	for(int i=0; i<=m; i++)
	    c[i][0] = 0;
	for(int j=0; j<=n; j++)
	    c[0][j] = 0;
	for(int i=1; i<= m; i++)
	{
		for(int j=1; j<=n; j++)
		{
			if(a[i-1] == b[j-1])
			    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];
			}
		}
	}
	return c[m][n];
}

//求解最长子序列的字符串 
char *buildlcs(char*a,char*b)
{
	int k,i=strlen(a),j=strlen(b);
	int c[N][N];
	k = lsclength(a,b,c);
	static char s[N];
	s[k] = '\0';
	while(k>0)
	{
		if(c[i][j] == c[i-1][j])
		    --i;
		else if(c[i][j] == c[i][j-1])
		    --j;
		else
		{
			s[--k] = a[i-1];
			--i;
			--j;
		}
	}
	return s;
 } 
int main()
{
	char *a = "abcbdb";
	char *b = "acbbabdbb";
	cout<<a<<endl;
	cout<<b<<endl;
	cout<<buildlcs(a,b)<<endl; 
	return 0;
}