HDU Common Subsequence

2017-11-16 1007

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

简介：

Common Subsequence

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)

Total Submission(s): 182 Accepted Submission(s): 109

Problem 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.
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.

Sample Input

abcfbc abfcab
programming contest 
abcd mnp

Sample Output

4
2
0



#include <iostream>
using namespace std;

int main()

{
    string a,b;

    int i,j;

    int c[500][500],al,bl;

    while(cin>>a>>b)

    {
        al = a.length();
        bl = b.length();

        for(i = 0; i < al ; i++)
        c[i][0] = 0;

        for(i = 0; i < bl ; i++)
        c[0][i] = 0;

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

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

        {

            if(a[i]==b[j])c[i+1][j+1] = c[i][j]+1;

            else

            {
               c[i+1][j+1] = (c[i][j+1]>=c[i+1][j]?c[i][j+1]:c[i+1][j]);

            }

        }
        cout<<c[i][j]<<endl;

    }

}

HDU Common Subsequence

Common Subsequence

热门文章

最新文章

相关电子书