Pagini recente » Cod sursa (job #586024) | Cod sursa (job #1806826) | Cod sursa (job #1895799) | Cod sursa (job #2592319) | Cod sursa (job #580330)
Cod sursa(job #580330)
#include <cstdio>
#include <cstring>
#define lmax 30010
#define cmax 262200
int n, l[22], last, st[cmax][22], conf, pi[22][lmax], pot[22][22], ok[22], prec[cmax][22];
char s[22][lmax];
void prefix(int x)
{
pi[x][1]=0;
int i, q=0;
for (i=2; i<=l[x]; i++)
{
while (q && s[x][q+1] !=s[x][i])
q=pi[x][q];
if (s[x][q+1]==s[x][i]) q++;
pi[x][i]=q;
}
}
void potrivire(int x, int y)
{
int i, q=0;
for (i=1; i<=l[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==l[x])
{
pot[y][x]=-1;
return;
}
}
pot[y][x]=q;
}
void solve()
{
int i, j, c, y, x;
for (i=0; i<(1<<n); i++)
for (j=1; j<=n; j++)
if (!ok[j])
if (i& (1<<(j-1)))
for (y=1; y<=n; y++)
if (y!=j && !ok[y])
if (i & (1<<(y-1)))
{
x=st[i^(1<<(j-1))][y]+pot[y][j];
if (x>=st[i][j])
{
st[i][j]=x;
prec[i][j]=y;
}
}
conf=(1<<n)-1;
for (i=1; i<=n; i++)
if (ok[i]) conf-=(1<<(i-1));
c=0;
for (i=1; i<=n; i++)
if (st[conf][i]>=c)
{
c=st[conf][i];
last=i;
}
}
void write(int conf, int ls)
{
if (!conf) return;
int p=prec[conf][ls];
if (!p)
printf("%s",s[ls]+1); else
{
write(conf^(1<<(ls-1)), p);
printf("%s", s[ls]+1+pot[p][ls]);
}
}
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", s[i]);
l[i]=strlen(s[i]);
for (j=l[i]; j>0; j--) s[i][j]=s[i][j-1];
}
for (i=1; i<=n; i++) prefix(i);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i!=j)
potrivire(i, j);
for (i=1; i<=n; i++)
for (j=1; j<=n; j++)
if (i!=j)
if (pot[j][i]==-1)
{
ok[i]=1;
break;
}
solve();
write(conf, last);
printf("\n");
return 0;
}