Pagini recente » Profil PregatireONI | Cod sursa (job #2747079) | Cod sursa (job #1551539) | Cod sursa (job #2842549) | Cod sursa (job #1014967)
#include<stdio.h>
#include<string.h>
#define NMAX 30007
#define MMAX (1 << 19)
#define LMAX 20
#define INF 1000000
int Pi[LMAX][LMAX], D[MMAX][LMAX], Pred[MMAX][LMAX], Lung[LMAX], C[LMAX][LMAX];
char a[LMAX][NMAX];
int B, n;
void prefix(char a[NMAX], int pi[NMAX], int n){
int x = 0;
pi[1] = 0;
for(int i = 2; i <= n; ++ i){
while(x > 0 && a[x + 1] != a[i])
x = pi[x];
if(a[x + 1] == a[i])
++ x;
pi[i] = x;
}
}
inline int KMP(int Indi, int Indj){
int x = 0;
for(int i = 1; i <= Lung[Indi]; ++ i){
while(x > 0 && a[Indi][i] != a[Indj][x + 1])
x = Pi[Indj][x];
if(a[Indi][i] == a[Indj][x + 1])
++ x;
if(x == Lung[Indj]){
B |= (1 << Indj);
return x;
}
}
return x;
}
void dinamic(){
for(int i = 1; i < (1 << n); ++ i)
for(int j = 0; j < n; ++ j){
D[i][j] = INF;
Pred[i][j] = -1;
}
for(int i = 0; i < n; ++ i)
D[(1 << i)][i] = Lung[i];
for(int i = 1; i < (1 << n); ++ i)
for(int j = 0; j < n; ++ j)
if(i & (1 << j))
for(int k = 0; k < n; ++ k)
if(k != j && (i & (1 << k))){
int Val = D[i ^ (1 << j)][k] - C[k][j] + Lung[j];
if(D[i][j] > Val){
D[i][j] = Val;
Pred[i][j] = k;
}
}
}
void afisare(int D[NMAX][LMAX]){
for(int i = 1; i < (1 << n); ++ i, printf("\n"))
for(int j = 0; j < n; ++ j)
printf("%d ", D[i][j]);
}
void afis(int x, int y) {
///printf("%d %d\n", x, y);
int Val = x - (1 << y);
if(Pred[x][y] == -1) {
printf("%s",a[y] + 1);
return;
}
afis(Val, Pred[x][y]);
for(int i = C[Pred[x][y]][y] + 1;i <= Lung[y]; ++ i)
printf("%c", a[y][i]);
}
int main(){
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d\n", &n);
for(int i = 0; i < n; ++ i){
gets(a[i] + 1);
Lung[i] = strlen(a[i] + 1);
prefix(a[i], Pi[i], Lung[i]);
}
for(int i = 0; i < n; ++ i)
for(int j = 0; j < n; ++ j)
if(i != j)
C[i][j] = KMP(i, j);
dinamic();
///afisare(C);
///afisare(D);
///afisare(Pred);
int Ans = INF, Poz = 0;
for(int i = 0; i < n; ++ i){
int Val = D[((1 << n) - 1) ^ B][i];
if(Val < Ans){
Ans = Val;
Poz = i;
}
}
afis(((1 << n) - 1) ^ B, Poz);
return 0;
}