Pagini recente » Cod sursa (job #1694717) | Cod sursa (job #903651) | Cod sursa (job #484203) | Cod sursa (job #3244951) | Cod sursa (job #1740583)
#include <fstream>
#include <iostream>
#include <cstring>
#define DIM 30010
using namespace std;
char s[19][DIM];
int p[19][DIM];
int A[19][19];
int out[19];
int Len[19];
int D[(1<<19)+1][20], T[(1<<19)+1][20];
int n;
ifstream fin ("adn.in");
ofstream fout("adn.out");
void prefix(int sir) {
int q = 0;
p[sir][1] = 0;
for (int i=2; s[sir][i] != 0; i++) {
while (q!=0 && s[sir][i] != s[sir][q+1])
q = p[sir][q];
if (s[sir][q+1] == s[sir][i])
q++;
p[sir][i] = q;
}
}
void drum(int stare, int b) {
if ((stare&(stare-1)) == 0) {
fout<<s[b]+1;
} else {
drum(stare - (1<<b), T[stare][b]);
// afisez ultimele A[T[stare][b]][b] caractere din s[b]
for (int i=Len[b]-A[T[stare][b]][b]+1; i<=Len[b];i++)
fout<<s[b][i];
}
}
int main () {
fin>>n;
for (int i=0;i<n;i++) {
fin>>s[i]+1;
Len[i] = strlen(s[i]+1);
prefix(i);
}
for (int i=0;i<n;i++)
for (int j=0;j<n;j++) {
if (i == j)
continue;
// caut cel mai lung prefix al lui j care este sufix al lui i
// practic caut daca sirul j se gaseste in sirul i
int q = 0;
for (int ii=1;s[i][ii]!=0;ii++) {
while (q!=0 && s[j][q+1] != s[i][ii])
q = p[j][q];
if (s[j][q+1] == s[i][ii])
q++;
if (q == Len[j]) {
q = p[j][ Len[j] ];
out[j] = 1;
}
if (ii == Len[i] && out[j] == 0) {
A[i][j] = Len[j]-q;
}
}
}
for (int i=0;i<n;i++) {
if (out[i] == 1) {
// elimin cuvantul i
for (int lin=i;lin<n-1;lin++) {
for (int col = 0; col < n; col++)
A[lin][col] = A[lin+1][col];
out[lin] = out[lin+1];
Len[lin] = Len[lin+1];
strcpy(s[lin]+1, s[lin+1]+1);
}
for (int col=i;col<n-1;col++)
for (int lin=0;lin<n;lin++)
A[lin][col] = A[lin][col+1];
n--;
i--;
}
}
/*
cout <<n<<"\n";
for (int i=0;i<n;i++) {
cout<<s[i]+1<<"\n";
}
for (int i=0;i<n;i++) {
for (int j=0;j<n;j++)
cout<<A[i][j] <<" ";
cout<<"\n";
}
*/
//ciclu (de fapt lant) hamiltonian de cost minim
int INF = 1 + (1<<8) + (1<<16) + (1<<24);
memset(D, 1, sizeof(D));
for (int stare = 1; stare<(1<<n); stare++) {
if ((stare &(stare-1)) == 0) {
for (int b=0;b<n;b++)
if ((stare >> b) & 1) {
D[stare][b] = Len[b];
break;
}
}
for (int b=0;b<n;b++) {
if ((stare >> b) & 1) {
// sunt in [stare][b] si adaug un nou nod
for (int nextb = 0; nextb<n; nextb++) {
if (((stare >> nextb) & 1) == 0) {
if (D[stare + (1<<nextb)][nextb] > D[stare][b] + A[b][nextb]) {
D[stare + (1<<nextb)][nextb] = D[stare][b] + A[b][nextb];
T[stare + (1<<nextb)][nextb] = b;
}
}
}
}
}
}
int sol = INF, u;
for (int b=0;b<n;b++) {
if (sol > D[(1<<n)-1][b]) {
sol = D[(1<<n)-1][b];
u = b;
}
}
drum((1<<n)-1, u);
// fout<<sol;
return 0;
}