Pagini recente » Cod sursa (job #1491415) | Cod sursa (job #1537441) | Cod sursa (job #795682) | Cod sursa (job #976504) | Cod sursa (job #1014486)
#include<stdio.h>
#include<string.h>
using namespace std;
int sol,c[25][25],d[300000][25],ant[300000][25],lg[25],pi[25][30010];
bool t[25];
char s[25][30005];
void pkmp(int x)
{
int i,k=0;
pi[x][1]=0;
for(i=2;i<=lg[x];++i)
{
while(k&&s[x][k+1]!=s[x][i])
k=pi[x][k];
if(s[x][k+1]==s[x][i])
k++;
pi[x][i]=k;
}
}
int kmp(int x,int y)
{
int i,k=0;
for(i=1;i<=lg[x];++i)
{
while(k && s[y][k+1]!=s[x][i])
k=pi[y][k];
if(s[y][k+1]==s[x][i])
k++;
if(k==lg[y])
return k;
}
return k;
}
void da(int conf,int p)
{
if(conf==(1<<p))
{
printf("%s",s[p]+1);
return;
}
da(conf^(1<<p),ant[conf][p]);
printf("%s",(s[p]+c[ant[conf][p]][p]));
return;
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
int i,j,q,n,l1,l2,nspe;
scanf("%u\n",&n);
for(i=0;i<n;++i)
{
gets(s[i]+1);
lg[i]=strlen(s[i]+1);
pkmp(i);
}
for(i=0;i<n;++i)
for(j=i+1;j<n;++j)
{
l1=kmp(i,j);
l2=kmp(j,i);
c[i][j]=l1;
c[j][i]=l2;
if(l1==lg[j])
t[j]=1;
else
if(l2==lg[i])
t[i]=1;
}
nspe=540000;
memset(d,nspe,sizeof(d));
for(i=0;i<n;++i)
if(t[i]==0)
{
sol+=(1<<i);
d[1<<i][i]=0;
}
for(q=1;q<(1<<n);q++)
for(i=0;i<n;i++)
if(t[i]==0 && (q&(1<<i)))
for(j=0;j<n;j++)
if(t[j]==0 && !(q&(1<<j)) && d[q^(1<<j)][j]>d[q][i]-c[i][j])
{
d[q^(1<<j)][j]=d[q][i]-c[i][j];
ant[q^(1<<j)][j]=i;
}
j=0;
for(i=1;i<n;++i)
if(d[sol][i]<d[sol][j])
j=i;
da(sol,j);
printf("\n");
return 0;
}