Pagini recente » Cod sursa (job #2755983) | Cod sursa (job #837816) | Cod sursa (job #931303) | Cod sursa (job #1727734) | Cod sursa (job #698227)
Cod sursa(job #698227)
#include <fstream>
#include <cstring>
#include <cstdio>
#define NMAx 30100
#define LMAx 19
#define PMAx 524300
#define oo (1<<30)
using namespace std;
char S[LMAx][NMAx];
int sol,Start,Finish,K,n,fail[NMAx],LEN[LMAx],viz[LMAx];
int Cost[LMAx][LMAx],D[PMAx][LMAx],T[LMAx][LMAx],T2[NMAx];
void copy_sol(int x) {
for(int i=1;i<=n;i++)
T2[i]=T[x][i];
}
int hamilton(int config,int last) {
if(config==(1<<last)) {
return LEN[last];
memset(T[last],0,sizeof(T[last]));
}
else
if(!D[config][last]) {
int e,i,k;
D[config][last]=oo;
for(int fiu=1;fiu<=n;fiu++)
if(fiu!=last&&!viz[fiu]&&(config&(1<<fiu)))
if(D[config][last]>(e = hamilton(config^(1<<last),fiu))+Cost[fiu][last]) {
memset(T[last],0,sizeof(T[last]));
for(k=0;T[fiu][k]&&k<LMAx;k++)
T[last][k]=T[fiu][k];
T[last][k]=fiu;
D[config][last]=e+Cost[fiu][last];
}
}
return D[config][last];
}
void kmp() {
int i,j,k,q;
for(i=1;i<=n;i++) {
// fail
for(j=2,q=0;j<=LEN[i];j++) {
while(q&&S[i][q+1]!=S[i][j])
q=fail[q];
if(S[i][q+1]==S[i][j])
++q;
fail[j]=q;
}
for(j=1;j<=n;j++) {
if(i==j)
continue;
// KMP
for(k=1,q=0;k<=LEN[j];k++) {
while(q&&S[i][q+1]!=S[j][k])
q=fail[q];
if(S[i][q+1]==S[j][k])
++q;
if(q==LEN[i]&&k<LEN[j]) {
Start^=(1<<i);
K--;
viz[i]=1;
q=0;
break;
}
}
Cost[j][i]=LEN[j]-q;
}
}
}
void citire() {
int i;
ifstream in("adn.in");
in>>n;
in.getline(S[0],LMAx);
for(i=1;i<=n;i++) {
in.getline(S[i]+1,NMAx);
LEN[i]=strlen(S[i]+1);
}
in.close();
}
void afis() {
int i,j;
ofstream out("adn.out");
K+=n-2;
for(i=K;i>=0;i--)
for(j=1;j<=Cost[T[Finish][i]][T[Finish][i-1]];j++)
out<<S[i][j];
/* for(;K;i=T[i],K--)
for(j=1;j<=Cost[i][T[i]];j++)
out<<S[i][j];*/
out<<S[Finish]+1;
out<<'\n';
out.close();
}
int main() {
int i;
citire();
Start=(1<<(n+1))-2;
kmp();
sol=oo;
for(i=1;i<=n;i++)
if(!viz[i])
if(sol>hamilton(Start,i)) {
sol=hamilton(Start,i);
Finish=i;
copy_sol(i);
}
afis();
return 0;
}