Cod sursa(job #197297)

Utilizator anna_bozianuBozianu Ana anna_bozianu Data 3 iulie 2008 12:02:35
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.48 kb
#include<stdio.h>
#include<string.h>
char s[20][30005];
long c[20][20],lung[20],prev[1<<18][20],cc[1<<18][20],inclus[20],N,M,
i,j,k,I8=1<<30,pi[20][30005];
void citire();
void prefix();
int KMP();
void pr_dinamica();
void print_sol();
int main()
{   
    freopen("adn.in","r",stdin);   
    freopen("adn.out","w",stdout);   
    citire();
    for(int i=0; i<N; i++)prefix();
    for(int i=0; i<N; i++)   
     for(int j=0; j<N; j++)
      { if(i==j)
         c[i][j]=0;
           else
         c[i][j]=KMP();
         if(c[i][j]==-1)
          inclus[j]=1;
      }
    pr_dinamica();
    print_sol();
    return 0;   
}

void citire()
{   
    scanf("%ld",&N);M=1<<N;I8=1<<30;
    for(int i=0; i<N; i++)   
    {   
        scanf("%s",s[i]+1);
        lung[i]=strlen(s[i]+1);
    }   
}

void prefix()
{   
    int k=0,lsir=lung[i];
    pi[i][1]=0;
    for(int q=2; q<=lsir; ++q)
    {   
        while(k>0 && s[i][q]!=s[i][k+1])
            k=pi[i][k];
        if(s[i][q]==s[i][k+1])
            k++;   
        pi[i][q]=k;
    }
}
int KMP()
{   
    int k=0,l1=lung[i],l2=lung[j],q;
    for(q=1; q<=l1; q++)
    {   
        while(k>0 && s[i][q]!=s[j][k+1])
            k=pi[j][k];
        if(s[i][q]==s[j][k+1])
            k++;   
        if(k==l2)
            return -1;
    }   
    return k;   
}   

void pr_dinamica()
{   
    M=1<<N;I8=1<<30;
    for(i=0;i<M;i++)
     for(j=0;j<N;j++)
         {   if(!(i&(1<<j)))
                cc[i][j]=I8;
            else  
                if(i==(1<<j))
                    cc[i][j]=lung[j];
                else  
                {   
                    cc[i][j]=I8;
                    for(k=0;k<N;k++)
                        if(cc[i^(1<<j)][k]!=I8 && cc[i][j]>cc[i^(1<<j)][k]+lung[j]-c[k][j])
                        {   
                            cc[i][j]=cc[i^(1<<j)][k]+lung[j]-c[k][j];
                            prev[i][j]=k;
                        }   
                }
         }
}   

void print_sol()
{   long h[20],t,cuv=0,pu,u=0,cs=0,min=I8;
    for(i=0;i<N;i++)
        if(!inclus[i])cs|=(1<<i);
    for(i=0; i<N; i++)
        if(!inclus[i] && min>cc[cs][i])
        {   
            min=cc[cs][i];
            u=i;
        }   
    while(cs)
    { h[++cuv]=u;
      pu=prev[cs][u];
      cs^=u;
      u=pu;
    }
    for(;cuv>1;cuv--)
    { t=lung[cuv]-c[h[cuv-1]][h[cuv]];
      for(i=0;i<=t;i++)printf("%c",s[cuv][i]);
    }
    printf("%s",s[h[1]]);
}