Pagini recente » Cod sursa (job #2302081) | Cod sursa (job #2516710) | Cod sursa (job #3001952) | Cod sursa (job #2322298) | Cod sursa (job #699885)
Cod sursa(job #699885)
#include <fstream>
#include <cstdio>
#include <cstring>
#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[PMAx][LMAx];
ofstream out("adn.out");
int hamilton(int config,int last) {
if(config==(1<<last))
return LEN[last];
else
if(!D[config][last]) {
int e;
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]) {
T[config][last]=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 config,int last) {
if(config==0)
return;
afis(config^(1<<last),T[config][last]);
if(config==(1<<last))
out<<S[last]+1;
else
out<<S[last]+LEN[last]-Cost[T[config][last]][last]+1;
}
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;
}
afis(Start,Finish);
out.close();
return 0;
}