Poj Solution 1934

http://poj.org/problem?id=1934

#include <stdio.h>
#include <vector>
#include <string.h>
#include <algorithm>
#include <set>
using namespace std;

int ans[81][81];
int from[81][81];
char route1[100],route2[100];
int n,m;

void doit()
{
    int i,j;
    for( i=0; i<=n; i++)
        ans[i][0] = 0;
    for( j=0; j<=m; j++)
        ans[0][j] = 0;

    for( i=1; i<=n; i++ )
    for( j=1; j<=m; j++ )
    {
        if( route1[i] == route2[j] )
        {
            ans[i][j] = ans[i-1][j-1] + 1;
            from[i][j] = 1;
        }
        else ans[i][j] = -1;

        if( ans[i-1][j] == ans[i][j] )
            from[i][j] |= 2;
        else if( ans[i-1][j] > ans[i][j] )
            from[i][j] = 2, ans[i][j] = ans[i-1][j];

        if( ans[i][j-1] == ans[i][j] )
            from[i][j] |= 4;
        else if( ans[i][j-1] > ans[i][j] )
            from[i][j] = 4, ans[i][j] = ans[i][j-1];
    }
}



struct cmp
{
    bool operator()(vector<char>* a,vector<char>* b)const
    {
        return std::lexicographical_compare( a->begin(), a->end(), b->begin(), b->end() );
    }
};

set< vector<char>*, cmp > word[81][81],output;

vector<char> w;

void search(int a,int b,int r)
{
    
    if( word[a][b].find( &w ) == word[a][b].end() )
    {
        vector<char>* p = new vector<char>( w );
        word[a][b].insert( p );
    }
    else return;

    if( r < 0 )
    {
        if( output.find( &w ) == output.end() )
        {
            vector<char>* p = new vector<char>( w );
            output.insert( p );
        }
        return;
    }

    if( from[a][b] & 1 )
    {
        w[r] = route1[a];
        search( a-1, b-1, r-1);
        w[r] = '';
    }

    if( from[a][b] & 2 )
        search( a-1, b, r );

    if( from[a][b] & 4 )
        search( a, b-1, r );
}

int main()
{
    int i,j;

    scanf("%s %s",route1+1,route2+1);

    n = strlen( route1+1 );
    m = strlen( route2+1 );

    doit();

    for(i=0;i<n;i++)
    for(j=0;j<m;j++)
        word[i][j].clear();

    w.resize(ans[n][m],'');

    search( n, m, ans[n][m]-1 );

    set< vector<char>*, cmp >::iterator iter, iter2;

    for( iter=output.begin(), i=0; iter != output.end() ; iter++,i++ )
    {
        if( !i || cmp()( *iter2, *iter ) )
        {    
            for(j=0;j<ans[n][m];j++)
                printf("%c",(*(*iter))[j] );
            printf("n");
        }
        iter2 = iter;
    }

    return 0;
    
}