Pagini recente » Cod sursa (job #860387) | Cod sursa (job #2093715) | Cod sursa (job #1089364) | Cod sursa (job #507741) | Cod sursa (job #57344)
Cod sursa(job #57344)
#include <stdio.h>
#include <string.h>
#define Ldim 30001
#define Ndim 19
int Next[Ndim][Ldim], A[Ndim][Ndim], S[Ndim], Sol[Ndim], Config[Ndim], Uz[Ndim], D[Ndim][Ndim], Tata[Ndim][Ndim];
int N, M, X, Cmax;
char T[Ndim][Ldim];
void Read();
void Solve();
void Print();
void Prefix(char *, int *);
void Back(int);
int Potrivire(char *, char *, int *);
int main()
{
Read();
Solve();
Print();
return 0;
}
void Read()
{
freopen("adn.in", "r", stdin);
int i;
for(scanf("%d\n", &N), i=1; i<=N; ++i)
{
scanf("%s", &T[i]);
Prefix(T[i], Next[i]);
S[i] = 1;
}
fclose(stdin);
}
void Solve()
{
int i, j, k, p;
for(i=1; i<=N; ++i)
for(j=1; j<=N; ++j)
if(i != j && S[i] && S[j])
{
A[i][j] = Potrivire(T[i], T[j], Next[j]);
if(A[i][j] == -1) S[j] = 0;
}
for(i=1; i<=N; ++i) X += S[i];
// Back(1);
for(i=2; i<=X; ++i)
{
for(j=1; j<=N; ++j)
if(S[j])
{
for(k=1; k<=N; ++k)
if(S[k] && k != j && D[i-1][k] + A[k][j] > D[i][j])
{
D[i][j] = D[i-1][k] + A[k][j];
Tata[i][j] = k;
}
}
}
for(i=1; i<=N; ++i)
if(S[i] && D[X][i] > Cmax)
{
Cmax = D[X][i];
p = i;
}
i = X;
while(i)
{
Config[i] = p;
p = Tata[i][p];
-- i;
}
}
void Print()
{
freopen("adn.out", "w", stdout);
printf("%s", T[Config[1]]);
int i, j, n;
for(i=2; i<=X; ++i)
{
n = strlen(T[Config[i]]);
for(j=A[Config[i-1]][Config[i]]-1; j<n; ++j)
printf("%c", T[Config[i]][j]);
}
fclose(stdout);
}
void Prefix(char *T, int *Next)
{
int n = strlen(T), q, k;
for(q=2, k=0; q<n; ++q)
{
while(k > 0 && T[k] != T[q]) k = Next[k];
if(T[k] == T[q]) ++ k;
Next[q] = k;
}
}
void Back(int k)
{
if(k == X + 1)
{
int i, cost = 0;
for(i=1; i<X; ++i)
cost += A[Sol[i]][Sol[i+1]];
if(cost >= Cmax)
{
Cmax = cost;
for(i=1; i<=X; ++i) Config[i] = Sol[i];
}
}
else
{
int i;
for(i=1; i<=N; ++i)
if(S[i] && !Uz[i])
{
Sol[k] = i;
Uz[i] = 1;
Back(k + 1);
Uz[i] = 0;
}
}
}
int Potrivire(char *T, char *P, int *Next)
{
int C[Ldim] = { 0 };
int q, k, n, m;
n = strlen(T);
m = strlen(P);
for(q=0, k=0; q<n; ++q)
{
while(k > 0 && P[k] != T[q])
k = Next[k];
if(P[k] == T[q]) ++ k;
C[q] = k;
if(k == m)
return -1;
}
return C[n-1] + 1;
}