Pagini recente » Cod sursa (job #2878438) | Cod sursa (job #1470567) | Cod sursa (job #1828718) | Cod sursa (job #710729) | Cod sursa (job #473932)
Cod sursa(job #473932)
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
int n;
char a[20][30003];
int len[20];
int dist[20][20];
int t[30003];
int calcDist (char a[], char p[], int n, int m)
{
int i, k;
memset (t, 0, sizeof (t));
t[1] = 0;
k = 0;
for (i = 2; i <= m; ++i)
{
while (k && p[i] != p[k + 1])
k = t[k];
if (p[i] == p[k + 1])
++k;
t[i] = k;
}
k = 0;
for (i = 1; i <= n; ++i)
{
while (k && a[i] != p[k + 1])
k = t[k];
if (a[i] == p[k + 1])
++k;
if (k == m)
return m;
}
return k;
}
void brut ()
{
int x[19];
int sol[19];
int mx = 0;
int i;
for (i = 1; i <= n; ++i)
x[i] = i;
int c = 0;
do
{
c = 0;
for (i = 2; i <= n; ++i)
c += dist[x[i - 1]][x[i]];
if (c >= mx)
{
mx = c;
for (i = 1; i <= n; ++i)
sol[i] = x[i];
}
}while (next_permutation (x + 1, x + n + 1));
//for (i = 2; i <= n; ++i)
// printf ("%d\n", dist[sol[i - 1]][sol[i]]);
printf ("%s", a[sol[1]] + 1);
for (i = 2; i <= n; ++i)
{
if (dist[sol[i - 1]][sol[i]] != len[sol[i]])
printf ("%s", a[sol[i]] + dist[sol[i - 1]][sol[i]] + 1);
}
printf ("\n");
}
int main ()
{
freopen ("adn.in", "r", stdin);
freopen ("adn.out", "w", stdout);
scanf ("%d\n", &n);
int i, j;
for (i = 1; i <= n; ++i)
{
scanf ("%s\n", &a[i]);
len[i] = strlen (a[i]);
for (j = len[i]; j > 0; --j)
a[i][j] = a[i][j - 1];
a[i][len[i] + 1] = 0;
// printf ("%s\n", a[i] + 1);
}
for (i = 1; i <= n; ++i)
for (j = 1; j <= n; ++j)
if (i != j)
dist[i][j] = calcDist (a[i], a[j], len[i], len[j]);
brut ();
return 0;
}