Common Subsequence【暑期集训G题】【最长公共子序列】

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, xij = 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.  The program input is from a text file. Each data set in the file contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct. 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.  Input abcfbc abfcab programming contest abcd mnpOutput 4 2 0Sample Input abcfbc abfcab programming contest abcd mnpSample Output 4 2 0

        这很明显就是一道求最长公共子序列的题（甚至没有给任何的陷阱）

对于求最长公共子序列，我们要知道它的算法：

        for(int i=1; i<=len_a; i++)

        {

            for(int j=1; j<=len_b; 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]);

                }

            }

        }

        但这题还有点要注意的就是，你的i与j最好从1开始，当然不是说你输入时的样式，而是指在上述的算法中的情况下，因为假如i=0或者j=0的时候，dp[i][j]=dp[i-1][j-1]+1 与   dp[i][j]=max(dp[i-1][j] , dp[i][j-1])会存在空情况。

 接着，送上完整代码：

#include <iostream> #include <cstdio> #include <string> #include <algorithm> using namespace std; string a,b; int len_a,len_b; int dp[1001][1001]; int main() { while(cin>>a>>b) { memset(dp, 0, sizeof(dp)); len_a=(int)a.length(); len_b=(int)b.length(); for(int i=1; i<=len_a; i++) { for(int j=1; j<=len_b; 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]); } } } printf("%d\n",dp[len_a][len_b]); } return 0; }

优化：

    稍微改进了些小操作，规范一下：

#include <iostream> #include <cstdio> #include <string> #include <algorithm> #define MT(a, b) memset(a, b, sizeof(a)) using namespace std; typedef long long ll; string a,b; int dp[1005][1005]; int main() { while(cin>>a>>b) { MT(dp, 0); 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]); } } } printf("%d\n",dp[a.size()][b.size()]); } return 0; }