Pagini recente » Cod sursa (job #155707) | Cod sursa (job #238037) | Cod sursa (job #1847092) | Cod sursa (job #1384117) | Cod sursa (job #203372)
Cod sursa(job #203372)
#include <stdio.h>
#include <string.h>
#define nmax 32
#define lgmax 32768
#define milion 1048576
char S[nmax][lgmax], W[nmax][lgmax];
int P[nmax][lgmax];
int ulti[milion], smax[milion];
int maxim[nmax][nmax], newmax[nmax][nmax];
int inclus[nmax], exista[nmax], neu[nmax], length[nmax], len2[nmax];
int N;
void makePrefix(int i)
{
int j, k;
for (j = 2; j <= length[i]; ++j)
{
k = P[i][j-1];
while (k > 0 && S[i][k+1] != S[i][j])
k = P[i][k];
if (S[i][k+1] == S[i][j])
k++;
P[i][j] = k;
}
}
void reconstruct(int v)
{
int i;
if (v)
{
reconstruct(v - (1<<ulti[v]));
if (v-(1<<ulti[v]) == 0)
for (i = 1; i <= len2[ ulti[v] ]; ++i)
printf("%c", W[ ulti[v] ][i]);
else
for (i = 1+newmax[ ulti[ v-(1<<ulti[v]) ] ][ ulti[v] ]; i <= len2[ ulti[v] ]; ++i)
printf("%c", W[ ulti[v] ][i]);
}
}
void makeKMP(int a, int b)
{
int t, k;
for (t = 1, k = 0; t <= length[a]; ++t)
{
while (S[b][k+1] != S[a][t] && k > 0)
k = P[b][k];
if (S[b][k+1] == S[a][t])
k++;
if (k == length[b])
{
inclus[b] = 1;
break;
}
}
maxim[a][b] = k;
}
int main()
{
int i, j, k, v, nr;
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d\n", &N);
for (i = 0; i < N; ++i)
{
S[i][0] = ' ';
scanf("%s\n", &S[i][1]);
}
for (i = 0; i < N; ++i)
length[i] = strlen(S[i])-1;
for (i = 0; i < N; ++i)
makePrefix(i);
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
if (i != j && inclus[i] == 0 && inclus[j] == 0)
makeKMP(i, j);
for (k = i = 0; i < N; ++i)
if (inclus[i] == 0)
{
for (neu[i] = k++, j = 0; j <= length[i]; ++j)
W[neu[i]][j] = S[i][j];
len2[neu[i]] = length[i];
}
for (i = 0; i < N; ++i)
for (j = 0; j < N; ++j)
if (inclus[i] == 0 && inclus[j] == 0 && i != j)
newmax[neu[i]][neu[j]] = maxim[i][j];
for (N = k, i = 0; i < N; ++i)
{
smax[1<<i] = 10;
ulti[1<<i] = i;
}
for (v = 1, N = k; v < (1<<N); ++v)
if (!smax[v])
{
for (i = 0; i < N; exista[i] = 0, ++i);
for (i = 0, nr = v; nr; nr >>= 1, ++i)
exista[i] = ((nr>>1)<<1 != nr);
for (i = 0; i < N; ++i)
if (exista[i] && smax[v-(1<<i)] && smax[v-(1<<i)] + newmax[ulti[v-(1<<i)]][i] > smax[v])
{
smax[v] = smax[v-(1<<i)] + newmax[ulti[v-(1<<i)]][i];
ulti[v] = i;
}
}
reconstruct((1<<N)-1);
printf("\n");
return 0;
}