Pagini recente » Cod sursa (job #186524) | Cod sursa (job #2433962) | Cod sursa (job #2257156) | Cod sursa (job #3131295) | Cod sursa (job #2517284)
#include<fstream>
#include<cstring>
#define INF 0x3f3f3f3f
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
int i,j,conf,l1,l2,n,pi,sol,c[20][20],d[500000][20],pred[500000][20],lg[20];
bool ok[20];
int poz[20][30100];
char s[20][30100];
inline void prefix(int x)
{
int i,k=0;
poz[x][1]=0;
for(i=2;i<=lg[x];++i)
{
while(k&&s[x][k+1]!=s[x][i])
k=poz[x][k];
if(s[x][k+1]==s[x][i])
++k;
poz[x][i]=k;
}
}
inline 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=poz[y][k];
if(s[y][k+1]==s[x][i])
++k;
if(k==lg[y])
return k;
}
return k;
}
inline void afiseaza(int conf,int p)
{
if(conf==(1<<p))
{
g<<(s[p]+1);
return;
}
afiseaza(conf^(1<<p),pred[conf][p]);
g<<(s[p]+1-c[pred[conf][p]][p]);
}
int main()
{
f>>n;
for(i=0;i<n;++i)
{
f>>(s[i]+1);
lg[i]=strlen(s[i]+1);
prefix(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])
ok[j]=1;
else
if(l2==lg[i])
ok[i]=1;
}
memset(d,INF,sizeof(d));
for(i=0;i<n;++i)
if(!ok[i])
{
sol+=(1<<i);
d[1<<i][i]=0;
}
for(conf=1;conf<(1<<n);++conf)
for(i=0;i<n;++i)
if(!ok[i]&&d[conf][i]<INF&&conf&(1<<i))
for(j=0;j<n;++j)
if(!ok[j]&&!(conf&(1<<j))&&d[conf^(1<<j)][j]>d[conf][i]+c[i][j])
{
d[conf^(1<<j)][j]=d[conf][i]+c[i][j];
pred[conf^(1<<j)][j]=i;
}
pi=0;
for(i=1;i<n;++i)
if(d[sol][i]<d[sol][pi])
pi=i;
afiseaza(sol,pi);
return 0;
}