【 알고리즘 도론 실험 4 】 동적 기획 - 최장 공통 서열 LCS

1280 단어
정말 중요해!!면접이든 실용이든 acm경기든!
원리는 dp에서 이해하기 쉬운...
#include <iostream>
#include <cstring>
#include <string>
using namespace std;

int c[100][100];
int b[100][100];
int countlength=0;

void LCS_Length (string x, string y)
{
	int m =x.size();
	int n =y.size();
	for (int i = 0; i <= m; i++)
		c[i][0] = 0;
	for (int i = 0; i <= n; i++)
		c[0][i] = 0;

	for (int i = 0; i < m; i++)
	{
		for (int j = 0; j < n; j++)
		{
			if (x[i] == y[j])
			{
				c[i + 1][j + 1] = c[i][j] + 1;
				b[i + 1][j + 1] = 0;
			}
			else if (c[i][j + 1] >= c[i + 1][j])
			{
				c[i + 1][j + 1] = c[i][j + 1];
				b[i + 1][j + 1] = 1;
			}
			else
			{
				c[i + 1][j + 1] = c[i + 1][j];
				b[i + 1][j + 1] = 2;
			}
		}
	}
}

void Print_LCS (string x, int i, int j)
{
	if ((i == 0) || (j == 0))
		return ;
	if (b[i][j] == 0)
	{
		Print_LCS (x, i - 1, j - 1);
		cout << x[i - 1] << ' ';
		countlength++;
	}
	else if (b[i][j] == 1)
		Print_LCS (x, i -1, j);
	else
		Print_LCS (x, i, j - 1);
}


int main()
{
	string x,y;

	while (cin >> x >> y)
	{
		LCS_Length (x, y);
		Print_LCS (x, x.size(), y.size());
		cout << endl;
		cout<<"   :"<<countlength<<endl;
	}
	return 0;
}

좋은 웹페이지 즐겨찾기