LCS及其回溯

/*
LCS

BDCABA
ABCBDAB

dp[1][2] = 1
dp[1][1] = 0
dp[2][1] = 0

//子串：连续
//子序列：可以不连续 
// LCS

dp[i][j]//第一个字符串在第i个字符前且第二个串在第j个字符前可构成的最长子序列的长度 

dp[i][j] = 			0  						i=0 || j=0
				dp[i-1][j-1]+1    		 str1[i]==str2[j]
			max(dp[i-1][j],dp[i][j-1])	 str1[i]!=str2[j]
*/
#include<cstdio>
#include<cstring>
#include<stack>
#include<algorithm>
using namespace std;
int main()
{
	char str1[20];
	char str2[20];
	scanf ("%s %s",str1+1,str2+1);
	str1[0] = str2[0] = '0';
	int l1 = strlen(str1)-1;
	int l2 = strlen(str2)-1;
	int dp[20][20] = {0};//0  						i=0 || j=0
	
	for (int i = 1 ; i <= l1 ; i++)
	{
		for (int j = 1 ; j <= l2 ; j++)
		{
			if (str1[i] == str2[j])//dp[i-1][j-1]+1    		 str1[i]==str2[j]
				dp[i][j] = dp[i-1][j-1] + 1;
			else
				dp[i][j] = max(dp[i-1][j],dp[i][j-1]);//max(dp[i-1][j],dp[i][j-1])	 str1[i]!=str2[j]
		}
	}
	
	//回溯求LCS 
	int pos1 = l1;
	int pos2 = l2;
	stack<char> S;
	while (pos1 > 0 && pos2 > 0)
	{
		if (str1[pos1] == str2[pos2])
		{
			S.push(str1[pos1]);
			pos1--;
			pos2--;
		}
		else if (dp[pos1-1][pos2] > dp[pos1][pos2-1])
			pos1--;
		else
			pos2--;
	}
	while (!S.empty())
	{
		printf ("%c%c",S.top(),(S.size() == 1) ? '\n' : ' ');
		S.pop();
	}
	printf ("%d\n",dp[l1][l2]);
	return 0;
}