Pagini recente » Cod sursa (job #1781649) | Cod sursa (job #2424976) | Cod sursa (job #413847) | Cod sursa (job #1607060) | Cod sursa (job #1453)
Cod sursa(job #1453)
#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;
}