UVA 531 Compromise

UVA_531

    本质上还是一个求最长公共子序列的问题，只不过需要打印路径。

#include<stdio.h>
#include<string.h>
#define MAXN 110
#define MAXM 40
char a[MAXN][MAXM], A, b[MAXN][MAXM], B;
int f[MAXN][MAXN], p[MAXN][MAXN], flag;
int init()
{
    int i;
    A = B = 1;
    for(;;)
    {
        if(scanf("%s", a[A]) != 1)
            return 0;
        if(a[A][0] == '#')
            break;
        A ++;
    }
    for(;;)
    {
        scanf("%s", b[B]);
        if(b[B][0] == '#')
            break;
        B ++;
    }
}
void printresult(int i, int j)
{
    if(!i || !j)
        return ;
    if(p[i][j] == 0)
    {
        printresult(i - 1, j - 1);
        if(flag)
            printf("");
        else
            flag = 1;
        printf("%s", a[i]);
    }
    else if(p[i][j] == -1)
        printresult(i - 1, j);
    else
        printresult(i, j - 1);
}
void solve()
{
    int i, j;
    memset(f, 0, sizeof(f));
    for(i = 1; i < A; i ++)
        for(j = 1; j < B; j ++)
        {
            if(strcmp(a[i], b[j]) == 0)
            {
                f[i][j] = f[i - 1][j - 1] + 1;
                p[i][j] = 0;
            }
            else
            {
                f[i][j] = f[i - 1][j];
                p[i][j] = -1;
                if( f[i][j - 1] > f[i][j])
                {
                    f[i][j] = f[i][j - 1];
                    p[i][j] = 1;
                }
            }
        }
    flag = 0;
    printresult(A - 1, B - 1);
    printf("\n");
}
int main()
{
    while(init())
    {
        solve();
    }
    return 0;
}