Pagini recente » Cod sursa (job #1832083) | Cod sursa (job #2174887) | Cod sursa (job #1380852) | Cod sursa (job #1265639) | Cod sursa (job #958)
Cod sursa(job #958)
#include <stdio.h>
#include <string.h>
#define nm 20
#define mm 300000
#define lm 30010
#define inf 1000000
void find(int, int);
int n, c[mm][nm], d[mm][nm], min, sol, crt, p[nm][lm], kmp[nm][nm], used[nm], l[nm];
char s[nm][lm], str[nm * lm];
int main()
{
int i, j, k, q, aux;
freopen("adn.in", "r", stdin);
freopen("adn.out", "w", stdout);
scanf("%d", &n);
for (i = 1; i <= n; ++i)
{
scanf(" %s ", &s[i]);
l[i] = strlen(s[i]);
min += l[i];
}
for (i = 1; i <= n; ++i)
{
p[i][1] = 0;
k = 0;
for (q = 2; q <= l[i]; ++q)
{
while(k > 0 && s[i][k] != s[i][q - 1])
k = p[i][k];
if (s[i][k] == s[i][q - 1])
++k;
p[i][q] = k;
}
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (i != j && !used[i] && !used[j])
{
k = 0;
for (q = 1; q <= l[i]; ++q)
{
while(k > 0 && s[j][k] != s[i][q - 1])
k = p[j][k];
if (s[j][k] == s[i][q - 1])
++k;
if (k == l[j])
{
used[j] = 1;
break;
}
}
kmp[i][j] = k;
}
for (aux = 1 << n - 1, i = 1; i <= n; ++i, aux /= 2)
{
c[aux][i] = l[i];
d[aux][i] = 0;
}
for (aux = 0, i = 1; i <= n; ++i)
aux = aux * 2 + 1 - used[i];
for (i = 1; i <= n; ++i)
if (!used[i])
{
if (!c[aux][i])
find(aux, i);
if (min > c[aux][i])
{
min = c[aux][i];
sol = i;
}
}
str[min] = '\0';
while(aux ^ (1 << n - sol))
{
crt = aux;
aux = crt ^ (1 << (n - sol));
for (i = l[sol]; i > kmp[d[crt][sol]][sol]; --i)
str[--min] = s[sol][i - 1];
sol = d[crt][sol];
}
for (i = 0; i < l[sol]; ++i)
str[i] = s[sol][i];
printf("%s\n", str);
return 0;
}
void find(int conf, int last)
{
int i, j, mask, aux;
c[conf][last] = inf;
aux = conf ^ (1 << (n - last));
for (mask = 1 << n - 1, i = 1; i <= n; ++i, mask /= 2)
if ((aux & mask) == mask)
{
if (!c[aux][i])
find(aux, i);
if (c[conf][last] > c[aux][i] + l[last] - kmp[i][last])
{
c[conf][last] = c[aux][i] + l[last] - kmp[i][last];
d[conf][last] = i;
}
}
}