poj 1458 Common Subsequence

深藏阁楼爱情的钟 2022-01-14 15:19 144阅读 0赞

[2019独角兽企业重金招聘Python工程师标准>>> ][2019_Python_] ![hot3.png][]

/*
    Common Subsequence
    Time Limit: 1000MS		Memory Limit: 10000K
    Total Submissions: 33061		Accepted: 12961
    
    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, 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.
    
    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
    
    Source
    Southeastern Europe 2003
    */
    
    #include <cstdio>
    #include <cstdlib>
    #include <cstring>
    #include <string>
    
    using namespace std;
    int dp[501][501] = {0};
    
    int main()
    {
        char str1[501], str2[501];
        while(scanf("%s%s", str1, str2) != EOF)
        {
            memset(dp, 0, sizeof(dp));
            for(int i = 0; i < strlen(str1); ++i)
            {
                if(str1[i] == str2[0])
                {
                    for(int j = i; j < strlen(str1); ++j)
                    {
                        dp[j][0] = 1;
                    }
                }
            }
    
            for(int i = 0; i < strlen(str2); ++i)
            {
                if(str2[i] == str1[0])
                {
                    for(int j = i; j < strlen(str2); ++j)
                    {
                        dp[0][j] = 1;
                    }
                }
            }
    
    
            for(int i = 1; i < strlen(str1); ++i)
                for(int j = 1; j < strlen(str2); ++j)
                {
                    if(str1[i] == str2[j])
                    {
                        dp[i][j] = dp[i - 1][j - 1] + 1;
                    }
                    else
                    {
                        dp[i][j] = dp[i - 1][j] > dp[i][j - 1] ? dp[i - 1][j] : dp[i][j - 1];
                    }
                }
            printf("%d\n", dp[strlen(str1) - 1][strlen(str2) - 1]);
        }
        return 0;
    }

转载于:https://my.oschina.net/locusxt/blog/140959

[2019_Python_]: https://my.oschina.net/u/2663968/blog/3061697
[hot3.png]: /images/20220114/75695a27d1834665a774baca85bbfdca.png