# 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;

}

```
This entry was posted in poj. Bookmark the permalink.