Contents

1. 1. 例如

• 和最长公共子串问题差不多，只不过允许不连续

  例如

abdecf
agbrc

输出
3 //abc

//hdu1159
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <climits>
#include <algorithm>
#define MAXN 1000
using namespace std;

char str1[MAXN], str2[MAXN];
int dp[MAXN][MAXN];

int main(){

    int i, j;
    while(scanf("%s%s", str1 + 1, str2 + 1) != EOF ){
        int len1 = strlen(str1 + 1);
        int len2 = strlen(str2 + 1);
        memset(dp, 0, sizeof(dp));
        for(i = 0; i <= len1; i++){
            dp[i][0] = 0;
        }
        for(i = 0; i <= len2; i++){
            dp[0][i] = 0;
        }
        for(i = 1; i <= len1; i++){
            for(j = 1; j <= len2; j++){
                if(str1[i] == str2[j])
                    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[len1][len2]);
        memset(str1, 0, sizeof(str1));
        memset(str2, 0, sizeof(str2));
    }
    return 0;
}