Cod sursa(job #337424)

Utilizator Cata99Putan Catalin Cata99 Data 3 august 2009 16:34:20
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.4 kb
#include <bitset>   
#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))   
  
char V[N_MAX][L_MAX];   
int P[N_MAX][N_MAX],L[N_MAX],A[1<<18][19];   
int 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;   
}