Cod sursa(job #2333669)

Utilizator shantih1Alex S Hill shantih1 Data 1 februarie 2019 18:50:13
Problema ADN Scor 100
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 1.73 kb
#include <iostream>
#include <fstream>

using namespace std;
ifstream fin("adn.in");
ofstream fout("adn.out");

int n,nr,i,j,a,b,l,m,k,ok,id;
int c[20][20],pi[30006],rz[262300][18],z[20];
char ch[524300][18];
string s[20],t[20],A,B;

void make_pi()
{
	int k=0;
	pi[1]=0;
	for(int i=2;i<=a;i++)
	{
		while(k>0 && A[k+1]!=A[i])
			k=pi[k];
		if(A[k+1]==A[i])
			k++;
		pi[i]=k;
	}
}
int match()
{
	int k=0;
	for(int i=1;i<=b;i++)
	{
		while(k>0 && A[k+1]!=B[i])
			k=pi[k];
		if(A[k+1]==B[i])
			k++;
		if(k==a)	ok=1;
	}
	return k;
}
int main() {
	
	fin>>n;
	for(i=1;i<=n;i++)
		fin>>t[i];
	
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j && t[i]!="" && t[j]!="")
			{
				A=" "+t[i];
				B=" "+t[j];
				a=(int)A.size()-1;
				b=(int)B.size()-1;
				
				ok=0;
				make_pi();
				nr=match();
				if(ok)	t[i]="";
			}
	m=n, n=0;
	for(i=1;i<=m;i++)
		if(t[i]!="")	s[++n]=t[i];
			
	for(i=1;i<=n;i++)
		for(j=1;j<=n;j++)
			if(i!=j)
			{
				A=" "+s[j];
				B=" "+s[i];
				a=(int)A.size()-1;
				b=(int)B.size()-1;
			
				make_pi();
				c[i][j]=match();
			}
	
	for(i=1;i<=n;i++)
		rz[1<<(i-1)][i]=(int)s[i].size(), ch[1<<(i-1)][i]='0'+i;
	
	m=(1<<n)-1;
	for(l=1;l<m;l++)
		for(i=1;i<=n;i++)
			if(l&(1<<(i-1)))
				for(j=1;j<=n;j++)
					if(!(l&(1<<(j-1))))
					{
						k=l+(1<<(j-1));
						
						nr=rz[l][i]-c[i][j]+(int)s[j].size();
						
						if(rz[k][j]==0)	rz[k][j]=660005;
						if(nr<rz[k][j])	
						{
							rz[k][j]=nr;
							ch[k][j]='0'+i;
						}
					}
	int rez=660005;
	for(i=1;i<=n;i++)
		if(rz[m][i]<rez)
			rez=rz[m][i],	id=i;
	
	l=m, m=n;
	while(id>0)
	{
		z[m--]=id;
		k=(1<<(id-1));
		id=ch[l][id]-'0';
		l-=k;
	}
	for(i=1;i<n;i++)
	{
		l=(int)s[z[i]].size()-c[z[i]][z[i+1]];
		for(j=1;j<=l;j++)
			fout<<s[z[i]][j-1];
	}
	fout<<s[z[n]]<<"\n";
}