POJ 1458 Common Subsequence(最長公共子序列LCS)

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  ij = 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      

就是求最長公共子序列，題意沒啥好講的，子序列和最長子序列是啥就不說了。

用一個二維數組dp[i][j]來表示到a串第i-1個和b串第j-1個字元的最長子序列長度，如果a[i] b[i]相等，說明必定在最長子序列裡，子序列長度++，如果不相等的話說明最長子序列長度在這個狀态不變，從前面兩個鄰近狀态挑大的那個。

dp問題要從鄰近的兩個值裡挑最大的，這就是dp的意義嘛，找出鄰近問題的最優解。

AC代碼：

#include <iostream>
#include <string>
#include <cstring>
using namespace std;
int dp[1010][1010];
int main()
{
    string a,b;

    while(cin>>a>>b)
    {
        memset(dp,0,sizeof(dp));
        for(int i=1;i<=a.size();i++)
        {
            for(int j=1;j<=b.size();j++)
            {
                if(a[i-1]==b[j-1]) dp[i][j]=dp[i-1][j-1]+1;
                else dp[i][j]=max(dp[i-1][j],dp[i][j-1]);
            }
        }
        cout<<dp[a.size()][b.size()]<<endl;
    }
    return 0;
}
           

還有個問題，就是如何按照字典序輸出最長子序列，這個就留待以後解決了。