Pagini recente » Cod sursa (job #323353) | Cod sursa (job #189293) | Cod sursa (job #1203201) | Cod sursa (job #2111212) | Cod sursa (job #1321303)
#include<fstream>
#include<vector>
#include<cstring>
#define MAXC 30002
#define MAXN 20
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
int PI[MAXC];
char CUVANT[MAXN][MAXC];
int n;
int G[MAXN][MAXN];
int alg(char *C1, char *C2) {
int i;
PI[1] = 0;
PI[0] = -1;
for(i=1; C2[i]; i++) {
int j=PI[i-1];
while(j!=-1 && C2[i]!=C1[j+1]) {
j = PI[j];
}
PI[i] = j + 1;
}
return PI[i-1];
}
int ssol, bestsol = -1;
bool TAKEN[MAXN];
int SOL[MAXN], BEST[MAXN];
void checksol() {
if(ssol > bestsol) {
bestsol = ssol;
for(int i=1; i<=n; i++) {
BEST[i] = SOL[i];
}
}
}
void hamilton(int nod, int pas) {
TAKEN[nod] = 1;
SOL[pas] = nod;
if(pas == n) {
checksol();
} else {
for(int i = 1; i<=n; i++) {
if(!TAKEN[i]) {
ssol += G[nod][i];
hamilton(i, pas+1);
ssol -= G[nod][i];
}
}
}
TAKEN[nod] = 0;
}
void citire() {
fin>>n;
for(int i=1; i<=n; i++) {
fin>>(CUVANT[i]+1);
CUVANT[i][0] = '#';
}
for(int i=1; i<=n; i++) {
for(int j=1; j<=n; j++) {
if(j == i) continue;
if(strstr(CUVANT[i]+1, CUVANT[j]+1)) {
G[i][j] = 0;
CUVANT[j][0] = 0;
} else {
G[i][j] = alg(CUVANT[i], CUVANT[j]);
}
}
}
}
void solve() {
for(int i=1; i<=n; i++) {
hamilton(i, 1);
}
}
int main() {
citire();
solve();
for(int i=n; i>=1; i--) {
for(int j=1; j<strlen(CUVANT[BEST[i]]) - G[BEST[i-1]][BEST[i]]; j++) {
fout<<(char)CUVANT[BEST[i]][j];
}
}
return 0;
}