[UVa] 531 - Compromise

Critical case: Normally you'd just check Part 1 against Part 2. But checking Part 2 agianst Part 1 might yield a better result.

#include <cstdio>
#include <iostream>
#include <map>
#include <string>
using namespace std;

int c[300][300], b[300][300], print1[300], print2[300];
int printer(int i, int j, int *x, int *print)
{
    int k=0;
    while (i>0 || j>0)
    {
        if (b[i][j]==1)
        {
            print[k++]=x[i];

            i--; j--;
        } else if (b[i][j]==2)
        {
            i--;
        } else
        {
            j--;
        }
    }
    return k;
}
int lcs(int *x, int *y, int size_a, int size_b)
{


    int m = size_a, n = size_b, i, j;
    for (i=0 ; i<=m ; i++)
    {
        for (j=0 ; j<=n ; j++)
        {
            c[i][j]=b[i][j]=0;
        }
    }

    for (i=1 ; i<m ; i++)
    {
        for (j=1 ; j<n ; j++)
        {
            if (x[i]==y[j])
            {
                c[i][j] = c[i-1][j-1]+1;
                b[i][j]=1;
            } else {
                if (c[i-1][j]>=c[i][j-1])
                {
                    c[i][j]=c[i-1][j];
                    b[i][j]=2;
                } else
                {
                    c[i][j]=c[i][j-1];
                    b[i][j]=3;
                }
            }
        }
    }
    return c[i-1][j-1];
}

class v
{
    public:
    string word;
    int id;
};

string s;
int main()
{
    while (1)
    {
        if (cin >> s)
        {
            map<string,int>l1;
            v wordList[300]={"",0};
            int i, l1_count=1, seq1_len=1, seq2_len=1, sizer, size1, size2, *print;
            int seq1[200], seq2[200];
            l1[s]=l1_count;
            wordList[l1_count].id = l1_count;
            wordList[l1_count].word=s;
            seq1[ seq1_len++ ] = l1_count++;
            while (cin >> s && s!="#")
            {
                if (l1[s])
                {
                    seq1[ seq1_len++ ] = l1[s];
                } else {
                    l1[ s ] = l1_count;
                    wordList[l1_count].id = l1_count;
                    wordList[l1_count].word = s;
                    seq1[ seq1_len++ ] = l1_count++;
                }
            }
            while (cin >> s && s!="#")
            {
                if (l1[s])
                {
                    seq2[ seq2_len++ ] = l1[s];
                } else {
                    l1[ s ] = l1_count;
                    wordList[l1_count].id = l1_count;
                    wordList[l1_count].word = s;
                    seq2[ seq2_len++ ] = l1_count++;
                }
            }
            size1 = lcs(seq1,seq2,seq1_len,seq2_len);
            printer(seq1_len-1,seq2_len-1, seq1, print1);
            size2 = lcs(seq2,seq1,seq2_len,seq1_len);
            printer(seq2_len-1,seq1_len-1, seq2, print2);

            if (size1>size2)
            {
                print = &print1[0];
                sizer=size1;
            } else
            {
                print = &print2[0];
                sizer=size2;
            }

            for (i=sizer-1 ; i>0 ; i--)
            {
                cout << wordList[print[i]].word << " ";
            }
            cout << wordList[print[i]].word << endl;

        } else {
            break;
        }
    }
    return 0;
}