POJ 1458：Common Subsequence

Common Subsequence

Time Limit: 1000MS		Memory Limit: 10000K
Total Submissions: 41957		Accepted: 16927

Description

A subsequence of a given sequence is the given sequence with some elements (possible none) left out. Given a sequence X = < x1, x2, ..., xm > another sequence Z = < z1, z2, ..., zk > is a subsequence of X if there exists a strictly increasing sequence < i1, i2, ..., ik > of indices of X such that for all j = 1,2,...,k, x_{i_j} = zj. For example, Z = < a, b, f, c > is a subsequence of X = < a, b, c, f, b, c > with index sequence < 1, 2, 4, 6 >. Given two sequences X and Y the problem is to find the length of the maximum-length common subsequence of X and Y.

Input

The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.

Output

For each set of data the program prints on the standard output the length of the maximum-length common subsequence from the beginning of a separate line.

Sample Input

abcfbc         abfcab
programming    contest 
abcd           mnp

Sample Output

4
2
0

这题三年之前估计就是看别人思路，自己写了一遍AC的，结果三年之后自己开始学习动态规划的时候，碰到了这种基础题目居然还是没想到思路，脸都不要了，真想敲自己脑袋啊。

题意很简单，求两个字符串的最长公共子序列。

标准的动态规划，用dp[i+1][j+1]表示到a的第i个字符，b的第j个字符时的最大长度。其实就是判断a[i]与b[j]是否相等，相等就在此基础之上加一。不相等就取dp[i][j+1]和dp[i+1][j]的最大值即可。

算法复杂度是O(i*j)，i、j为两个字符串的长度。

代码：

#include<iostream>
#include<string>
#include<cstring>
using namespace std;

int dp[500][500];

int main()
{
	string a,b;
	while(cin>>a>>b)
	{
		memset(dp,0,sizeof(dp));
		int len1=a.length();
		int len2=b.length();

		int i,j;

		for(i=0;i<len1;i++)
		{
			for(j=0;j<len2;j++)
			{
				if(a[i]==b[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]);
			}
		}

		cout<<dp[len1][len2]<<endl;
	}
	
	return 0;
}

总结的话，就是自己为什么没能想到用dp[i][j]的数组来表示呢，我还咋想用dp[i]表示在第二个字符串中到第i个字符时的长度，然后之后在逐渐查找，但这样麻烦啊麻烦啊。所以总结就是自己为什么没能想到用这种方式表示呢？自己为什么没能想到用这种方式表示呢？

总而言之，只能记住这种最长公共子序列的方法，记住了这种方法，自己脑袋里的数据库也算多了一点，以后再遇到这类问题的时候还想不到的话，真的就要敲自己脑袋了。