UVa 10405 Longest Common Subsequence

Dynamic Programming的基本題 LCS

DJWS的LCS筆記
洪朝貴老師的動態規劃講義

這題我寫了兩種解法
LCS() 是一般的作法，最清楚直接。
LCS_save_memory() 是針對記憶體優化過的算法。

這題唯一要小心的點就是UVa的字串中包含空格。

	/**
	* UVa 10405 Longest Common Subsequence
	* Author: chchwy
	* Last Modified: 2010.04.01
	*/
	#include<iostream>
	using namespace std;
	enum {MAX_LENGTH = 1000};
	int LCS_save_memory(string& str1, string& str2)
	{
	int path[2][MAX_LENGTH + 1];
	int cur = 0, prev = 1;
	memset(path, 0, sizeof(path));
	for (int i = 1; i <= str1.size(); ++i)
	{
	for (int j = 1; j <= str2.size(); ++j)
	{
	if ( str1[i - 1] == str2[j - 1] )
	{
	path[cur][j] = path[prev][j - 1] + 1;
	}
	else
	{
	path[cur][j] = max(path[cur][j - 1], path[prev][j]);
	}
	}
	swap(cur, prev);
	}
	return path[prev][str2.size()];
	}
	int LCS(string& str1, string str2)
	{
	int path[MAX_LENGTH + 1][MAX_LENGTH + 1];
	for (int i = 0; i < str1.size(); ++i)
	path[i][0] = 0;
	for (int i = 0; i < str2.size(); ++i)
	path[0][i] = 0;
	for (int i = 1; i <= str1.size(); ++i)
	{
	for (int j = 1; j <= str2.size(); ++j)
	{
	if ( str1[i - 1] == str2[j - 1] )
	{
	path[i][j] = path[i - 1][j - 1] + 1;
	}
	else
	{
	path[i][j] = max(path[i][j - 1], path[i - 1][j]);
	}
	}
	}
	return path[str1.size()][str2.size()];
	}
	int main()
	{
	#ifndef ONLINE_JUDGE
	freopen("10405.in", "r", stdin);
	#endif
	string str1, str2;
	while ( getline(cin, str1) && getline(cin, str2) )
	{
	printf("%d\n", LCS(str1, str2) );
	// printf("%d\n", LCS_save_memory(str1, str2) );
	}
	return 0;
	}

view raw 10405.cpp hosted with ❤ by GitHub