Cod sursa(job #203423)

Utilizator tvladTataranu Vlad tvlad Data 16 august 2008 11:49:38
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.3 kb
#include <cstdio>
#include <cstring>

const int NMAX = 20;
const int LMAX = 30002;
const int CFGMAX = 262130;
const int INF = 1000000000;
#define NMAX 20
#define LMAX 30002
#define CFGMAX 262130
#define INF 1000000000
const int mask[] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072};

int N;
int length[NMAX],P[NMAX][LMAX];
char seq[NMAX][LMAX];
int com[NMAX][NMAX];
bool mark[NMAX];
int C[CFGMAX][NMAX],last[CFGMAX][NMAX];

void read_data() {
	char aux[5];
	fgets(aux,5,stdin);
	sscanf(aux,"%d",&N);
	for (int i=0; i<N; i++) {
		scanf("%s",seq[i]+1);
		length[i]=strlen(seq[i]+1);
	}
}

void prefix ( char *sir, int lung, int *P ) {
	int k=0;
	P[1]=0;
	for (int q=2; q<=lung; ++q) {
		while (k>0 && sir[q]!=sir[k+1]) k=P[k];
		if (sir[q]==sir[k+1]) k++;
		P[q]=k;
	}
}

int KMP ( char *sir, int lsir, char *subsir, int lsubsir, int *P ) {
	int k=0;
	for (int q=1; q<=lsir; ++q) {
		while (k>0 && sir[q]!=subsir[k+1]) k=P[k];
		if (sir[q]==subsir[k+1]) k++;
		if (k==lsubsir) return -1;
	}
	return k;
}

void DP() {
	int cfg = 1 << N;
	for (int i=0; i<cfg; ++i)
		for (int j=0; j<N; ++j)
			if (!(i&mask[j]))
				C[i][j]=INF; else
			if(i==mask[j])
				C[i][j]=length[j];
			else {
				C[i][j]=INF;
				for(int k=0; k<N; ++k)
					if (C[i^mask[j]][k]!=INF && C[i][j]>C[i^mask[j]][k]+length[j]-com[k][j]) {
						C[i][j]=C[i^mask[j]][k]+length[j]-com[k][j];
						last[i][j]=k;
					}
			}
}

void write_string ( char *s, int begin, int end ) {
	for (int i=begin; i<=end; ++i) fputc(s[i],stdout);
}

void write ( int i, int j ) {
	if(i==mask[j])
		write_string(seq[j],1,length[j]);
	else {
		write(i^mask[j],last[i][j]);
		write_string(seq[j],com[last[i][j]][j]+1,length[j]);
	}
}

void write_solution() {
	int cfg=0, min=INF, p=-1;
	for (int i=0; i<N; i++)
		if (mark[i]==false)
			cfg|=mask[i];
	for (int i=0; i<N; i++)
		if (mark[i]==false && min>C[cfg][i]) {
			min=C[cfg][i];
			p=i;
		}
	write(cfg,p);
}

int main() {
	freopen("adn.in","r",stdin);
	freopen("adn.out","w",stdout);
	read_data();
	for(int i=0; i<N; i++) {
		prefix(seq[i],length[i],P[i]);
	}
	for(int i=0; i<N; i++) {
		for(int j=0; j<N; j++) {
			if(i==j)
				com[i][j]=0;
			else {
				com[i][j]=KMP(seq[i],length[i],seq[j],length[j],P[j]);
				if(com[i][j]==-1)
					mark[j]=true;
			}
		}
	}
	DP();
	write_solution();
	return 0;
}