Cod sursa(job #1024200)

Utilizator scipianusFMI Ciprian Olariu scipianus Data 8 noiembrie 2013 13:30:04
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.61 kb
#include <fstream>
#include <cstring>
#include <iostream>
using namespace std;
int n, Pi[30100], ns[20], cost[20][20], best[18][263000], Next[18][263000], sol;
char s[20][30100];
bool eliminat[20];

inline void CreateGraph()
{
	int i, j, k = 0, p;
	for( i = 0; i < n; ++i)
	{
		for( j = 0; j < n; ++j)
		{
			memset(Pi, 0, sizeof(Pi));
			Pi[1] = 0;
			k = 0;
			for( p = 2; p <= ns[i]; ++p)
			{
				while( k && s[j][k + 1] != s[i][p]) k = Pi[k];
				if(s[j][k + 1] == s[i][p]) k++;
				Pi[p] = k;
			}
			cost[i][j] = Pi[ns[i]];
		}
	}
	for( i = 0; i < n; ++i)
	{
		for( j = 0; j < n; ++j)
		{
			if(i == j)
				continue;
			memset(Pi, 0, sizeof(Pi));
			Pi[1] = 0;
			k = 0;
			for( p = 2; p <= ns[i]; ++p)
			{
				while( k && s[i][k + 1] != s[i][p]) k = Pi[k];
				if(s[i][k + 1] == s[i][p]) k++;
				Pi[p] = k;
			}
			k = 0;
			for( p = 1; p <= ns[j]; ++p)
			{
				while(k && s[i][k + 1] != s[j][p]) k=Pi[k];
				if(s[i][k + 1] == s[j][p]) k++; //s-au potrivit
				if(k == ns[i]) //am gasit intreg pattern-ul
				{
					eliminat[i]=true;
					p=ns[j];
				}
			}
		}
	}
}

inline string FindCycle()
{
	int i, j, conf, first, aux, conflim = 0;
	string rez;
	for( conf = 0; conf < (1<<n); ++conf)
		for( i = 0; i < n; ++i)
			best[i][conf] = 1000000000;
	for( i = 0; i < n; ++i)
		if(!eliminat[i])
			conflim += (1 << i);
	for( i = 0; i < n; ++i)
		best[i][( 1 << i)] = ns[i];
	for( conf = 0; conf < (1<<n); ++conf)
	{
		for( i = 0; i < n; ++i)
		{
			if(eliminat[i])
				continue;
			if(conf & (1 << i))
			{
				for( j = 0; j < n; ++j)
				{
					if(eliminat[j])
						continue;
					if(!(conf & (1 << j)))
					{
						if(best[j][conf + (1 << j)] > ns[j] - cost[j][i] + best[i][conf])
						{
							best[j][conf + (1 << j)] = ns[j] - cost[j][i] + best[i][conf];
							Next[j][conf + (1 << j)] = i;
						}
					}
				}
			}
		}
	}
	first = -1;
	sol = 1000000000;
	for( i = 0; i < n; ++i)
	{
		if(eliminat[i])
			continue;
		if(best[i][conflim] < sol)
		{
			sol = best[i][conflim];
			first = i;
		}
	}
	for( i = 1; i <= ns[first]; ++i)
		rez += s[first][i];
	conf = conflim;
	while(Next[first][conf])
	{
		aux = first;
		first = Next[first][conf];
		conf -= (1 << aux);
		for( i = cost[aux][first] + 1; i <= ns[first]; ++i)
			rez += s[first][i];
	}
	return rez;
}

int main()
{
	int i;
	ifstream fin("adn.in");
	fin >> n;
	for(i = 0; i < n; ++i)
	{
		fin >> (s[i] + 1);
		ns[i] = strlen(s[i] + 1);
	}
	fin.close();
	
	CreateGraph();
	
	ofstream fout("adn.out");
	fout << FindCycle() << "\n";
	fout.close();
	return 0;
}