Cod sursa(job #694987)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 28 februarie 2012 09:47:22
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.05 kb
#include <fstream>
#include <cstring>
#include <cstdio>
#define NMAx 30100
#define LMAx 19
#define PMAx 524300
#define oo (1<<30)
using namespace std;

char S[LMAx][NMAx];
int sol,Start,Finish,K,n,fail[NMAx],LEN[LMAx],viz[LMAx];
int Cost[LMAx][LMAx],D[PMAx][LMAx],T[LMAx],T2[NMAx];

void copy_sol() {
	
	for(int i=1;i<=n;i++)
		T2[i]=T[i];
	
}
int hamilton(int config,int last) {
	
	if(config==(1<<last))
		return LEN[last];
	else
	if(!D[config][last]) {
		
		int e;
		D[config][last]=oo;
		for(int fiu=1;fiu<=n;fiu++)
			if(fiu!=last&&!viz[fiu]&&(config&(1<<fiu)))
				if(D[config][last]>(e = hamilton(config^(1<<last),fiu))+Cost[fiu][last]) {
					T[last]=fiu;
					D[config][last]=e+Cost[fiu][last];
					}
		
		}
	
	return D[config][last];
	
}
void kmp() {
	
	int i,j,k,q;
	
	for(i=1;i<=n;i++) {
		
		// fail
		for(j=2,q=0;j<=LEN[i];j++) {
			
			while(q&&S[i][q+1]!=S[i][j])
				q=fail[q];
			
			if(S[i][q+1]==S[i][j])
				++q;
			
			fail[j]=q;
			}
		
		for(j=1;j<=n;j++) {
			
			if(i==j)
				continue;
			
			// KMP
			for(k=1,q=0;k<=LEN[j];k++) {
				
				while(q&&S[i][q+1]!=S[j][k])
					q=fail[q];
				
				if(S[i][q+1]==S[j][k])
					++q;
				
				if(q==LEN[i]&&k<LEN[j]) {
					Start^=(1<<i);
					K--;
					viz[i]=1;
					q=0;
					break;
					}
				}
			
			Cost[j][i]=LEN[j]-q;
			
			}
		}
	
}
void citire() {
	
	int i;
	ifstream in("adn.in");
	in>>n;
	in.getline(S[0],LMAx);
	
	for(i=1;i<=n;i++) {
		in.getline(S[i]+1,NMAx);
		LEN[i]=strlen(S[i]+1);
		}
	
	in.close();
	
}
void afis() {
	
	int i,j;
	ofstream out("adn.out");
	
	K+=n-1;
	for(i=Finish,j=0;j<K;i=T2[i],j++)
		T[T2[i]]=i;
	
	for(;K;i=T[i],K--)
		for(j=1;j<=Cost[i][T[i]];j++)
			out<<S[i][j];
	out<<S[Finish]+1;
	out<<'\n';
	out.close();
	
}
int main() {
	
	int i;
	citire();
	
	Start=(1<<(n+1))-2;
	kmp();
	
	sol=oo;
	for(i=1;i<=n;i++)
		if(!viz[i])
			if(sol>hamilton(Start,i)) {
				sol=hamilton(Start,i);
				Finish=i;
				copy_sol();
				}
	
	afis();
	
	return 0;

}