Pagini recente » Cod sursa (job #2773470) | Cod sursa (job #457191) | Cod sursa (job #2930754) | Cod sursa (job #2660952) | Cod sursa (job #3200634)
#include <fstream>
#define inf 540001
using namespace std;
ifstream fin ("adn.in");
ofstream fout ("adn.out");
string s[18],sir;
int poz,p,ok,n,i,j,pr[30001],nr,minim,l[18][18],dp[(1<<18)][18];
short int t[(1<<18)][18];
void f (int poz,int conf)
{
if (t[conf][poz]==-1)
{
for (int j=1; j<s[poz].size (); j++)
fout<<s[poz][j];
}
else
{
int ant=t[conf][poz];
f (ant,conf-(1<<poz));
for (int j=l[ant][poz]; j>0; j--)
fout<<s[poz][s[poz].size ()-j];
}
}
bool match (string &a,string &b)
{
int l=0;
pr[1]=0;
for (int i=2; i<a.size (); i++)
{
while (l>0&&a[i]!=a[l+1])
l=pr[l];
if (a[i]==a[l+1])
l++;
pr[i]=l;
}
l=0;
for (int i=1; i<b.size (); i++)
{
while (l>0&&b[i]!=a[l+1])
l=pr[l];
if (a[l+1]==b[i])
l++;
if (l==a.size ()-2)
return 1;
}
return 0;
}
int pref (string &a,string &b)
{
int l=0;
pr[1]=0;
for (int i=2; i<a.size (); i++)
{
while (l>0&&a[i]!=b[l+1])
l=pr[l];
if (a[i]==b[l+1])
l++;
pr[i]=l;
}
return l;
}
int main ()
{
fin>>n;
for (i=0; i<n; i++)
{
fin>>sir;
s[i]="0";
s[i]+=sir;
}
nr=0;
for (i=0; i<n; i++)
{
ok=1;
for (j=0; j<n; j++)
{
if (i==j)
continue;
if (match (s[i],s[j]))
{
ok=0;
break;
}
}
if (ok==1)
s[nr++]=s[i];
}
n=nr;
for (i=0; i<n; i++)
{
for (j=0; j<n; j++)
{
if (i==j)
continue;
l[i][j]=(s[j].size ()-1)-pref (s[i],s[j]);
}
}
for (p=0; p<(1<<n); p++)
{
for (i=0; i<n; i++)
dp[p][i]=inf;
}
for (i=0; i<n; i++)
{
dp[(1<<i)][i]=s[i].size ();
t[(1<<i)][i]=-1;
}
for (p=1; p<(1<<n); p++)
{
for (i=0; i<n; i++)
{
if (!((p>>i)&1)||dp[p][i]!=inf)
continue;
nr=p-(1<<i);
for (j=0; j<n; j++)
{
if (!((nr>>j)&1))
continue;
if (dp[nr][j]+l[j][i]<dp[p][i])
{
dp[p][i]=dp[nr][j]+l[j][i];
t[p][i]=j;
}
}
}
}
minim=inf;
for (i=0; i<n; i++)
{
if (dp[(1<<n)-1][i]<minim)
{
minim=dp[(1<<n)-1][i];
poz=i;
}
}
f (poz,(1<<n)-1);
return 0;
}