HDU1159(LCS)

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cstdio>

using namespace std;

char str1[1000], str2[1000];

int length[1000][1000]; //str1的左边i个字符形成的子串，与str2左边的j个字符形成的子串的最长公共子序列的长度(i, j从0 开始算），

int main(void)

{

    while (cin>>str1>>str2)

    {

        int len_one = strlen(str1), len_two = strlen(str2), i, j;

        for (i = 0; i <= len_one; i++)

            length[i][0] = 0;       //str1前i个字符的字串串，str2为0，字串为0

        for (j = 0; j <= len_two; j++)

            length[0][j] = 0;       //str2前j个字符的字串串，str2为0，字串为0

        for(i=1;i<=len_one;i++)

            for (j = 1; j <= len_two; j++)

            {

                if (str1[i - 1] == str2[j - 1])     //如果两者相等。此时这个字符是两个字符串的一个LCS

                    length[i][j] = length[i - 1][j - 1] + 1;

                else                            //如果两者不等，那么这个字符可能是length[i - 1][j], length[i][j - 1]其中一个的一个LCS

                    length[i][j] = max(length[i - 1][j], length[i][j - 1]);

            }

        cout << length[len_one][len_two] << endl;

    }

    return 0;

}
巴特西

HDU1159(LCS)

最新文章

热门文章
