Cod sursa(job #1014626)

Utilizator thewildnathNathan Wildenberg thewildnath Data 22 octombrie 2013 22:26:58
Problema ADN Scor 20
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.22 kb
#include<stdio.h>
#include<string.h>

int n,l[20],pi[20][30002],c[20],f[20][20],ds[30002][20],fct[300002][20];
char v[20][30002];

void funct()
{
    int i,j,ls;
    for(i=1;i<=n;++i)
    {
        ls=0;
        for(j=2;j<=l[i];++j)
        {
            while(ls && v[i][ls+1]!=v[i][j])
                ls=pi[i][ls];
            if(v[i][ls+1]==v[i][j])
                ++ls;
            pi[i][j]=ls;
        }
    }
}

int kmp(int x,int y)
{
    int i,ls=0;
    for(i=1;i<=l[x];++i)
    {
        while(ls && v[y][ls+1]!=v[x][i])
            ls=pi[y][ls];
        if(v[y][ls+1]==v[x][i])
            ++ls;
        if(ls==l[y])
            return ls;
    }
    return ls;
}

void afis(int x,int y)
{
    if(x==(1<<y))
    {
        printf("%s",v[y]+1);
        return;
    }
    afis(x^(1<<y),fct[x][y]);
    printf("%s",(v[y]+1+f[fct[x][y]][y]));
}

int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
    int i,j,li,lj,ls,sol=0,max,aux;
    scanf("%d\n",&n);
    for(i=1;i<=n;++i)
    {
        gets(v[i]+1);
        l[i]=strlen(v[i]+1);
    }

    funct();

    for(i=1;i<=n;++i)
    {
        for(j=i+1;j<=n;++j)
        {
            li=kmp(i,j);
            f[i][j]=li;

            lj=kmp(j,i);
            f[j][i]=lj;

            if(li==l[j])
                c[j]=1;
            else if(lj==l[i])
                c[i]=1;
        }
    }

    memset(ds,2000000000,sizeof(ds));

    for(i=1;i<=n;++i)
        if(!c[i])
        {
            sol+=(1<<i);
            ds[1<<i][i]=0;
        }
    max=(1<<n);
    for(ls=1;ls<max;++ls)
    {
        for(i=1;i<=n;++i)
        {
            if(!c[i] && (ls&(1<<i)))
                for(j=1;j<=n;++j)
                    if(!c[j] && !(ls&(1<<j)))
                    {
                        if(ds[ls^(1<<j)][j]>ds[ls][i]-f[i][j])
                        {
                            ds[ls^(1<<j)][j]=ds[ls][i]-f[i][j];
                            fct[ls^(1<<j)][j]=i;
                        }
                    }
        }
    }
    ls=0;
    for(i=2;i<=n;++i)
        if(ds[sol][i]<ds[sol][ls])
            ls=i;

    afis(sol,ls);
    printf("\n");

    return 0;
}