Cod sursa(job #958)

Utilizator sims_glAlexandru Simion sims_gl Data 12 decembrie 2006 12:18:02
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#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;
            }
        }
}