Cod sursa(job #699957)

Utilizator okros_alexandruOkros Alexandru okros_alexandru Data 29 februarie 2012 22:12:31
Problema ADN Scor 80
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.91 kb
#include <fstream>
#include <cstdio>
#include <cstring>
#define NMAx 30100
#define LMAx 20
#define PMAx 530300
#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[PMAx][LMAx];
ofstream out("adn.out");


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[last][fiu]) {
					T[config][last]=fiu;
					D[config][last]=e+Cost[last][fiu];
					}
		}
	
	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[i][j]=LEN[i]-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 config,int last) {
	
	if(config==0)
		return;
	
	afis(config^(1<<last),T[config][last]);
	
	if(config==(1<<last))
		out<<S[last]+1;
	else {
		int tata=T[config][last];
		out<<S[last]+LEN[last]-Cost[last][tata]+1;
		}
		
}
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;
				}
	
	afis(Start,Finish);
	
	out.close();
	
	return 0;

}