두 문자열의 최대 공통 서열과 최대 공통 문자열

1. 최대 공통 하위 시퀀스
예를 들어 BDCABA와 ABCBDAB의 최대 공통 하위 시퀀스는 BCBA입니다.
두 개의 점차적인 하표 서열과str1[i1]=str2[j1],str1[i2]=str2[j2],......str1[ik]=str2[jk].
동적 계획을 사용하여 해답을 구하다.
DP[i][j]는str1의 전 i개 원소와str2의 전 j개 원소가 구성할 수 있는 가장 큰 서열의 길이를 나타낸다.
str1=BDCABA
str2=ABCBDAB
그러면 DP[1]=0
DP[1][2]=1
DP[3][3]=2
그래서 얻을 수 있는 상태 방정식은 다음과 같다.
0, i=0 또는 j=0
DP[i][j]=               DP[i-1][j-1]+1,  str1[i]==str2[j]
Max(DP[i+1][j],DP[i][j+1]), 기타
구현은 다음과 같습니다.

#include
#include 
#include 
#include 
using namespace std;


int Max(int a, int b)
{
	return a > b ? a : b;
}

vector LongestSubSeq(char *str1, char *str2)
{
	int size1 = strlen(str1);
	int size2 = strlen(str2);
	vector result;
	int max = 0;//      ，                    result 
	vector> DP(size1+1, vector(size2+1, 0));
	for (int i = 0; i < size1; i++)
		for (int j = 0; j < size2; j++)
		{
			if (str1[i] == str2[j]) DP[i + 1][j + 1] = DP[i][j] + 1;
			else DP[i + 1][j + 1] = Max(DP[i+1][j],DP[i][j+1]);
			if (DP[i + 1][j + 1] > max)
			{
				max = DP[i + 1][j + 1];
				result.push_back(str1[i]);
			}
		}
	return result;
}

int main(void)
{
	char a[] = "abcdefghijklmn";
	char b[] = "acefnq";
	vector re = LongestSubSeq(a, b);
	for (int i = 0; i < re.size(); i++)
		cout << re[i];
	cout << endl;
	return(0);
}

2. 최대 공통 하위 문자열
예를 들어 BDCABA와 ABCBDAB의 가장 큰 공통 문자열은 BD와 AB이다.
두 개의 점차적인 하표 서열과str1[i1]=str2[j1],str1[i2]=str2[j2],......str1[ik]=str2[jk].매번 1씩 증가합니다.
동적 기획으로도 할 수 있다.str1[i]==str2[j]이면DP[i][j]=DP[i-1][j-1]+1이다.
만약str1[i]!=str2[j]이면 DP[i][j]=0.이것이 차이점이다.

#include
#include 
#include 
#include 
using namespace std;


int Max(int a, int b)
{
	return a > b ? a : b;
}

vector LongestSubSeq(char *str1, char *str2)
{
	int size1 = strlen(str1);
	int size2 = strlen(str2);
	vector result;
	int max = 0;//      ，                    result 
	vector> DP(size1+1, vector(size2+1, 0));
	for (int i = 0; i < size1; i++)
		for (int j = 0; j < size2; j++)
		{
			if (str1[i] == str2[j]) DP[i + 1][j + 1] = DP[i][j] + 1;
			else DP[i + 1][j + 1] = 0;
			if (DP[i + 1][j + 1] == max)
			{
				result.pop_back();
				result.push_back(str1[i]);
			}
			if (DP[i + 1][j + 1] > max)
			{
				max = DP[i + 1][j + 1];
				result.push_back(str1[i]);
			}
		}
	cout << max << endl;
	return result;
}


int main(void)
{
	char a[] = "abcdefgabcdefgh";
	char b[] = "acdefnqabcdefgh";
	vector re = LongestSubSeq(a, b);
	for (int i = 0; i < re.size(); i++)
		cout << re[i];
	cout << endl;
	return(0);
}