Cod sursa(job #1454)

Utilizator webspiderDumitru Bogdan webspider Data 13 decembrie 2006 18:46:04
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.42 kb
#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int modn = 49999;
const int bzh  = 17;

int hash[ modn ];
int modif;
char sir[18][30002];
int ad[19][19];
int prevc[19];
int x,y;
int prev[19];
int mark[19];
int maxl=1000000, lc, tata, hsh;
int m1,m2,l,put;
int hsh1;

int n;

void dfs( int nodc, int lc, int adc )
{
	int i;
	mark[nodc] = 1;
	if ( adc == n-1 ) 
		if ( lc < maxl )
	{
		memcpy( prev, prevc, sizeof( prevc ) );
		maxl = lc;
		modif = 1;
	}
	for ( i = 1; i <= n; i ++ )
		if ( ad[ nodc ][ i ] && !mark[i] )
		{
			prevc[ nodc ] = i;	
			dfs( i, lc+strlen( sir[i] )-ad[nodc][i], adc+1 );
		}
	mark[nodc] = 0;
}

int powc( int a, int b)
{
	int r = 1;
	int i;
	for ( i = 1 ; i <= b ; i ++ )
	{
		r*=a;
		r%=modn;
	}
	
	return r;
}

int main()
{
	int i,j;
	freopen("adn.in","r",stdin);
	freopen("adn.out","w",stdout);
	scanf("%d\n", &n);
	
	for ( i = 1; i <= n; i ++ )
		scanf("%s\n", &sir[i] );
	
	for ( i = 1; i <= n; i++ )
		for ( j = 1 ; j <= n; j ++)
			if ( i != j && strlen( sir[i] ) <= strlen( sir[j] ) )
	{
		m1 = strlen( sir[i] );
		m2 = strlen( sir[j] );
		for ( l = 0 ; l < m1; l++)
		{
			hsh += ( sir[i][l]*powc( bzh, m1-l-1)) % modn;
			hsh %= modn;
			
			hsh1+= ( sir[j][l]*powc( bzh, m1-l-1)) % modn;
			hsh1 %= modn;
		}
		if ( hsh == hsh1 ) mark[i] = 1;
		else
		for ( l = m1; l < m2; l ++ )
		{
			hsh1 -= ( sir[j][l-m1]*powc( bzh, m1-1 ) )%modn;
			hsh1 *= bzh; hsh1 %= modn;
			hsh1 += sir[j][l]; hsh1 %= modn;
			if ( hsh1 < 0 ) hsh1 += modn;
			
			if ( hsh == hsh1 ) { mark[i] = 1; break; }
		}
		hsh = 0;
		hsh1 = 0;
	}
	
	for (i=1; i<=n; i++)
		for ( j=1; j<=n; j++)
			if ( i != j && ( !mark[i] && !mark[j] ) )
	{
		m1 = strlen( sir[i] );
		m2 = strlen( sir[j] );
		for ( l = m1-1, put = 0 ; l>=0; l --, put ++ )
		{
			hsh+=(sir[i][l]*powc( bzh, put ))%modn;
			hsh%=modn;
			if ( hsh < 0 ) hsh += modn;
			hash[hsh] = put;
		}
		hsh = 0;
		for ( l = 0; l < m2; l ++ )
		{
			hsh*=bzh;
			hsh%=modn;
			hsh += sir[j][l];
			hsh%=modn;
			if ( hash[hsh] )
				if ( hash[hsh] == l )
					ad[i][j] = l+1;
		}
		hsh = 0;
		bzero( hash, sizeof( hash ) );
	}
	for ( i=1; i<=n; i++)
	{
		modif = 0;
		dfs(i,strlen( sir[i] ),1);
		if ( modif ) tata = i;
	}
	for ( i = 1; i<=n; i++ )
	{
		if ( i == n ) ad[ tata ][ prev[tata] ] = 0;
		for ( j = 0 ; j < strlen( sir[tata] ) - ad[ tata ][ prev[tata] ]; j++)
			printf("%c", sir[tata][j]);
		tata = prev[tata];
	}

	fclose(stdin);
	fclose(stdout);
	return 0;
}