Pagini recente » Cod sursa (job #1606019) | Cod sursa (job #1700961) | Cod sursa (job #1610502) | Cod sursa (job #2956519) | Cod sursa (job #1071789)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <cstring>
#include <memory.h>
#define Present(config, poz) ((config) & (1 << poz))
#define Out(config, poz) ((config) ^ (1 << poz))
#define tata Tat[conf][nod]
using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");
const int Nmax = 19;
const int Mmax = 30100;
const int oo = 0x3f3f3f3f;
int N, sters, maxconf, PI[Nmax][Mmax], Lg[Nmax], CST[Nmax][Nmax], DP[(1 << Nmax)][Nmax], Tat[(1 << Nmax)][Nmax];
char s[Nmax][Mmax];
void Build_PI(int i)
{
for(int q = 2, k = 0; q <= Lg[i]; q++)
{
while(k && s[i][k+1] != s[i][q])
k = PI[i][k];
if(s[i][k+1] == s[i][q]) k++;
PI[i][q] = k;
}
}
int KMP(int x, int y)
{
int q = 0;
for(int i = 1; i <= Lg[y]; i++)
{
while(q && s[x][q+1] != s[y][i])
q = PI[x][q];
if(s[x][q+1] == s[y][i]) q++;
if(q == Lg[x])
{
sters |= (1 << x);
return q;
}
}
return q;
}
void Afisare(int conf, int nod)
{
if(tata == -1)
{
fout<<s[nod] + 1;
return;
}
Afisare(Out(conf, nod), tata);
for(int i = CST[tata][nod] + 1; i <= Lg[nod]; i++)
fout<<s[nod][i];
}
int main()
{
fin>>N;
for(int i=0; i < N; i++)
{
fin>>(s[i] + 1);
Lg[i] = strlen(s[i] + 1);
Build_PI(i);
}
for(int i = 0; i < N; i++)
for(int j = 0; j < N; j++)
if(i != j) CST[i][j] = KMP(j, i);
memset(DP, oo, sizeof DP);
memset(Tat, -1, sizeof Tat);
for(int i=0; i < N; i++)
DP[(1 << i)][i] = Lg[i];
maxconf = (1 << N); int nr;
for(int conf = 0; conf < maxconf; conf++)
for(int i = 0; i < N; i++)
if(Present(conf, i))
for(int j = 0; j < N; j++)
if(i != j && Present(conf, j))
if(DP[conf][i] > (nr = DP[Out(conf, i)][j] - CST[j][i] + Lg[i]))
{
DP[conf][i] = nr;
Tat[conf][i] = j;
}
int finalconf = (maxconf - 1) & (~sters), psol = 0;
for(int i=1; i < N; i++)
if(DP[finalconf][psol] > DP[finalconf][i]) psol = i;
Afisare(finalconf, psol);
return 0;
}