题目

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

题解

>最长公共子序列<
模板题,基本上看输入输出就足够了……

代码

/*
By:OhYee
Github:OhYee
HomePage:http://www.oyohyee.com
Email:oyohyee@oyohyee.com

かしこいかわいい？
エリーチカ！
要写出来Хорошо的代码哦~
*/

#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <string>
#include <iostream>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <map>
#include <set>
using namespace std;

const int maxn = 1005;

//最长公共子序列
//输入字符串a 及其长度 字符串b 及其长度 保存最长公共子序列的数组
//字符从0开始
int LCS(char *a,char *b,char s[] = NULL) {
    int len1 = strlen(a);
    int len2 = strlen(b);
    char *aa = a - 1;
    char *bb = b - 1;
    //声明二维数组
    int * m = new int[(len1 + 1)*(len2 + 1)];
    int **dp = new int *[len1 + 1];
    for(int i = 0;i <= len1;i++)
        dp[i] = m + i*(len2 + 1);
    //初始化
    for(int i = 0;i <= len1;i++)
        dp[i][0] = 0;
    for(int i = 0;i <= len2;i++)
        dp[0][i] = 0;
    //动态规划
    for(int i = 1;i <= len1;i++)
        for(int j = 1;j <= len2;j++)
            if(aa[i] == bb[j])
                dp[i][j] = dp[i - 1][j - 1] + 1;
            else
                dp[i][j] = max(dp[i - 1][j],dp[i][j - 1]);
    /*for(int i = 0;i <= len1;i++){
    for(int j = 0;j <= len2;j++)
    printf("%d\t",dp[i][j]);
    printf("\n");
    }*/
    //如果c未传值
    if(s == NULL)
        return dp[len1][len2];
    //逆序推出一条符合串
    int ans = dp[len1][len2];
    int x = len1;
    int y = len2;
    int it = ans;
    s[it] = '\0';
    while(it) {
        if(dp[x - 1][y] == it) {
            x--;
            continue;
        }
        if(dp[x][y - 1] == it) {
            y--;
            continue;
        }
        s[--it] = aa[x];
        x--;
        y--;
    }
    return ans;
}

char a[maxn],b[maxn];

bool  Do() {
    if(scanf("\n%s%s",a,b) == EOF)
        return false;

    printf("%d\n",LCS(a,b));
    return true;
}

int main() {
    while(Do());
    return 0;
}