POJ 2250 Compromise (DP,最长公共子序列)

Description

Input

Output

Sample Input

die einkommen der landwirte
sind fuer die abgeordneten ein buch mit sieben siegeln
um dem abzuhelfen
muessen dringend alle subventionsgesetze verbessert werden
#
die steuern auf vermoegen und einkommen
sollten nach meinung der abgeordneten
nachdruecklich erhoben werden
dazu muessen die kontrollbefugnisse der finanzbehoerden
dringend verbessert werden
#

Sample Output

die einkommen der abgeordneten muessen dringend verbessert werden

题意  求两端文本的最长公共子单词序列  直接lcs增量法可以得出   打印路劲也是直接递归就行

#include<cstdio>
#include<cstring>
using namespace std;
const int N = 105, L = 35;
char a[N][L], b[N][L];
int pre[N][N], d[N][N], n, m, la, lb, flag;
void lcs()
{
    memset (d, 0, sizeof (d)); memset (pre, 0, sizeof (pre));
    for (int i = 1; i < la; ++i)
        for (int j = 1; j < lb; ++j)
            if (!strcmp (a[i], b[j]))
            {
                d[i][j] = d[i - 1][j - 1] + 1;
                pre[i][j] = 1;
            }
            else if (d[i - 1][j] > d[i][j - 1])
            {
                d[i][j] = d[i - 1][j];
                pre[i][j] = 2;
            }
            else
            {
                d[i][j] = d[i][j - 1];
                pre[i][j] = 3;
            }
}

void print (int i, int j)
{
    if (pre[i][j] == 1)
    {
        print (i - 1, j - 1);
        if (flag) flag = 0;
        else printf (" ");
        printf ("%s", a[i]);
    }
    else if (pre[i][j] == 2)
        print (i - 1, j);
    else if (pre[i][j] == 3)
        print (i, j - 1);
}

int main()
{
    while (scanf ("%s", a[1]) != EOF)
    {
        la = 1; lb = 0; flag = 1;
        while (scanf ("%s", a[++la]), a[la][0] != '#');
        while (scanf ("%s", b[++lb]), b[lb][0] != '#');
        lcs();
        print (la - 1, lb - 1);
        printf ("\n");
    }
    return 0;
}

POJ 2250 Compromise (DP,最长公共子序列),布布扣,bubuko.com

POJ 2250 Compromise (DP,最长公共子序列)

原文：http://blog.csdn.net/iooden/article/details/38390619