Cod sursa(job #203372)

Utilizator vlad.maneaVlad Manea vlad.manea Data 15 august 2008 21:18:39
Problema ADN Scor 40
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.45 kb
#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;
}