Cod sursa(job #1758988)

Utilizator hackerinoHackerino hackerino Data 18 septembrie 2016 12:33:05
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.7 kb
#include <cstdio>
#include <algorithm>
#include <cstring>
#define II inline
#define FOR(i,a,b) for(int i=a;i<=b;++i)
#define IN  "adn.in"
#define OUT "adn.out"
#define N_MAX 1<<5
#define L_MAX 1<<15
#define oo 1<<30
#define p(x) (1<<(x-1))
using namespace std;
char V[N_MAX][L_MAX];
int P[N_MAX][N_MAX],L[N_MAX],A[1<<18][19],pi[L_MAX],N,K;
II void print(int x,int y);
II void scan(){
  freopen(IN,"r",stdin);
  freopen(OUT,"w",stdout);
  scanf("%d\n",&N);
  FOR(i,1,N){
   scanf("%s",&V[i]);
   for(int j=0;V[i][j] != '\0';L[i] = j,++j);
  }
 K=(1<<N)-1;
}
II void prefix(char N[],int n){
 int k=0;pi[0]=0;
 FOR(i,1,n){
  while(k && N[k] != N[i]) k = pi[k-1];
  if(N[k]==N[i])++k;
  pi[i] = k;
 }
}
II int kmp(char N[],char M[],int n,int m){
 int q = 0;
 FOR(i,0,m){
  while(q && N[q] != M[i]) q=pi[q-1];
  if(N[q] == M[i]) ++q;
  if(q==n+1) return oo;
 }
 return q;
}
II void solve(){
  memset(A,100,sizeof(A));
  A[0][0] = 0;
  FOR(i,1,N)
  FOR(j,1,N)
  if(i!=j && (K & p(j) ) ){
   prefix(V[j],L[j]);
   P[i][j] = kmp(V[j],V[i],L[j],L[i]);
   if(P[i][j] == oo){K ^= p(j);}
  }
  FOR(i,1,K){
   FOR(j,1,N){
    if(!p(j) & (i||K) ) continue;
    FOR(k,0,N){
     if(k==j) continue;
     A[i][j]=min(A[i][j],A[i^p(j)][k]-P[k][j]);
    }
   }
  }
 int poz(0);A[K][0]=oo;
 FOR(i,1,N){if(A[K][i] < A[K][poz]) poz=i;}
 print(K,poz);
}

II void print(int x,int y)
{
    if(x == p(y))
    {
        printf("%s",V[y]);
        return;
    }
    FOR(i,1,N)
        if(A[x ^ p(y)][i] - P[i][y] == A[x][y])
        {
            print(x ^ p(y),i);
            printf("%s",V[y]+P[i][y]);
            return;
        }
}
int main(){
 scan();
 solve();
 return 0;
}