Pagini recente » Cod sursa (job #276526) | Cod sursa (job #3260454) | Cod sursa (job #499418) | Cod sursa (job #1225171) | Cod sursa (job #502105)
Cod sursa(job #502105)
#include<algorithm>
#include<string.h>
using namespace std;
#define N_MAX 19
#define L_MAX 30005
#define MAX 1<<30
char cuv[N_MAX][L_MAX];
int prefix[N_MAX][N_MAX];
int dp[1<<N_MAX][N_MAX];
int t[1<<N_MAX][N_MAX];
int kmp[L_MAX];
int i,j,n;
void Prefix(char *c)
{
int k=0,cl=strlen(c+1);
for(int i=2;i<=cl;i++)
{
while(k>0&&c[k+1]!=c[i])
k=kmp[k];
if(c[k+1]==c[i])
k++;
kmp[i]=k;
}
}
int KMP(char *a,char *b)
{
int k=0,a1=strlen(a+1),b1=strlen(b+1);
Prefix(b);
for(int i=1;i<=a1;i++)
{
while(k>0&&b[k+1]!=a[i])
k=kmp[k];
if(b[k+1]==a[i])
k++;
if(k==b1)
{
return -1;
}
}
return k;
}
void REC(int config,int j)
{
if(j==0)
return ;
int tata=t[config][j];
REC(config-(1<<j),tata);
if(t==0)
printf("%s",cuv[j]+1);
else
printf("%s",cuv[j]+1+prefix[tata][j]);
}
int main()
{
freopen("adn.in","r",stdin);
freopen("adn.out","w",stdout);
scanf("%d\n",&n);
for(i=1;i<=n;i++)
{
cuv[i][0]='*';
scanf("%s",(cuv[i]+1));
}
int N=0;
for(i=1;i<=n;i++)
{
int inSide=0;
for(j=1;j<=n;j++)
{
if(i==j)
continue;
if(KMP(cuv[j],cuv[i])==-1)
{
inSide=1;
break;
}
}
if(!inSide)
{
N++;
memcpy(cuv[N],cuv[i],sizeof(cuv[N]));
}
}
n=N;
for(i=1;i<=n;i++)
{
for(j=1;j<=n;j++)
{
if(i==j)
continue;
prefix[i][j]=KMP(cuv[i],cuv[j]);
}
}
int config,k;
for(config=1;config<(1<<(n+1));config++)
for(j=1;j<=n;j++)
dp[config][j]=-(1<<20);
for(i=1;i<=n;i++)
dp[(1<<i)][i]=0;
for(config=2;config<(1<<(n+1));config+=2)
{
for(j=1;j<=n;j++)
{
if((config&(1<<j))==0)
continue;
for(k=1;k<=n;k++)
{
if(k==j)
continue;
if((config&(1<<k))==0)
continue;
if(dp[config][j]<dp[config-(1<<j)][k]+prefix[k][j])
{
dp[config][j]=dp[config-(1<<j)][k]+prefix[k][j];
t[config][j]=k;
}
}
}
}
int Max=0,ind=0;
for(i=1;i<=n;i++)
if(dp[(1<<(n+1))-2][i]>Max)
Max=dp[(1<<(n+1))-2][i],ind=i;
REC((1<<(n+1))-2,ind);
return 0;
}