Cod sursa(job #356997)

Utilizator ProtomanAndrei Purice Protoman Data 17 octombrie 2009 18:56:44
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <algorithm>
#include <stdio.h>
#include <vector>
#include <string>

#define MAX 32000
#define pb push_back

using namespace std;

int n, minGs = LONG_MAX, loc, poz;
int pi[MAX];
int up[20][20];
char strConf[20][MAX];
vector <string> strAdn;
int lungSol[(1 << 18)][20];

inline void prefix(string str)
{
	int k = 0;
	for (int i = 2; i < str.size(); i++)
	{
		for (; k && str[i] != str[k + 1]; k = pi[k]);

		if (str[i] == str[k + 1])
			k++;

		pi[i] = k;
	}
}

inline int kmp(string strMic, string strMare)
{
	prefix(strMic);

	int k = 0, incl = 0;
	for (int i = 1; i < strMare.size(); i++)
	{
		for (; k && strMare[i] != strMic[k + 1]; k = pi[k]);

		if (strMare[i] == strMic[k + 1])
			k++;

		if (k == strMic.size() - 1)
		{
			k = pi[k];
			incl = 1;
		}
	}

	poz = k;
	return incl;
}

inline void afis(int conf, int loc)
{
	int cf = conf - (1 << loc);

	int puse = 0;
	for (int ul = 0; ul < n; ul++)
		if (lungSol[cf][ul] + strAdn[loc].size() - 1 - up[ul][loc] == lungSol[conf][loc])
		{
			afis(cf, ul);

			for (int i = up[ul][loc] + 1; i < strAdn[loc].size(); i++)
				printf("%c", strAdn[loc][i]);

			return;
		}

	for (int i = 1; i < strAdn[loc].size(); i++)
		printf("%c", strAdn[loc][i]);
}


int main()
{
	freopen("adn.in", "r", stdin);
	freopen("adn.out", "w", stdout);

	scanf("%d\n", &n);

	for (int i = 1; i <= n; i++)
	{
		fgets(strConf[i] + 1, MAX, stdin);
	
		strConf[i][strlen(strConf[i] + 1)] = 0;
		strConf[i][0] = '-';
	}

	for (int i = 1; i <= n; i++)
	{
		strAdn.pb(strConf[i]);
	
		for (int j = 1; j <= n; j++)
			if (i != j)
				if (kmp(strConf[i], strConf[j]))
				{
					strAdn.pop_back();

					break;
				}
	}
	
	n = strAdn.size();

	for (int i = 0; i < (1 << n); i++)
		for (int j = 0; j < n; j++)
			lungSol[i][j] = LONG_MAX;

	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			kmp(strAdn[i], strAdn[j]);

			up[j][i] = poz;
		}

		lungSol[1 << i][i] = strAdn[i].size() - 1;
	}

	for (int conf = 1; conf < (1 << n); conf++)
		for (int ul = 0; ul < n; ul++)
			if (conf & (1 << ul))
				for (int pun = 0; pun < n; pun++)
					if (!(conf & (1 << pun)))
						lungSol[conf | (1 << pun)][pun] = min((unsigned) lungSol[conf | (1 << pun)][pun], 
							lungSol[conf][ul] + strAdn[pun].size() - 1 - up[ul][pun]);

	for (int i = 0; i < n; i++)
		if (lungSol[(1 << n) - 1][i] < minGs)
		{
			minGs = lungSol[(1 << n) - 1][i];
			loc = i;
		}

	afis((1 << n) - 1, loc);

	fclose(stdin);
	fclose(stdout);
	return 0;
}