Cod sursa(job #580330)

Utilizator antoanelaAntoanela Siminiuc antoanela Data 12 aprilie 2011 22:55:10
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.86 kb
#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;
}