Cod sursa(job #1014486)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 22 octombrie 2013 19:39:37
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 1.81 kb
#include<stdio.h>
#include<string.h>
using namespace std;
int  sol,c[25][25],d[300000][25],ant[300000][25],lg[25],pi[25][30010];
bool t[25];
char s[25][30005];
void pkmp(int x)
{
    int i,k=0;
    pi[x][1]=0;
    for(i=2;i<=lg[x];++i)
    {
        while(k&&s[x][k+1]!=s[x][i])
        k=pi[x][k];
        if(s[x][k+1]==s[x][i])
        k++;
        pi[x][i]=k;
    }
}
int kmp(int x,int y)
{
    int i,k=0;
    for(i=1;i<=lg[x];++i)
    {
        while(k && s[y][k+1]!=s[x][i])
        k=pi[y][k];
        if(s[y][k+1]==s[x][i])
        k++;
        if(k==lg[y])
        return k;
    }
    return k;
}
void da(int conf,int p)
{
    if(conf==(1<<p))
    {
    printf("%s",s[p]+1);
        return;
    }
    da(conf^(1<<p),ant[conf][p]);
    printf("%s",(s[p]+c[ant[conf][p]][p]));
    return;
}
int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
    int i,j,q,n,l1,l2,nspe;
    scanf("%u\n",&n);
    for(i=0;i<n;++i)
    {
        gets(s[i]+1);
        lg[i]=strlen(s[i]+1);
        pkmp(i);
    }
    for(i=0;i<n;++i)
    for(j=i+1;j<n;++j)
    {
        l1=kmp(i,j);
        l2=kmp(j,i);
        c[i][j]=l1;
        c[j][i]=l2;
        if(l1==lg[j])
        t[j]=1;
        else
        if(l2==lg[i])
        t[i]=1;
    }
     nspe=540000;
    memset(d,nspe,sizeof(d));
    for(i=0;i<n;++i)
    if(t[i]==0)
    {
        sol+=(1<<i);
        d[1<<i][i]=0;
    }
    for(q=1;q<(1<<n);q++)
    for(i=0;i<n;i++)
    if(t[i]==0 && (q&(1<<i)))
    for(j=0;j<n;j++)
    if(t[j]==0 && !(q&(1<<j)) && d[q^(1<<j)][j]>d[q][i]-c[i][j])
    {
        d[q^(1<<j)][j]=d[q][i]-c[i][j];
        ant[q^(1<<j)][j]=i;
    }
    j=0;
    for(i=1;i<n;++i)
    if(d[sol][i]<d[sol][j])
    j=i;
    da(sol,j);
    printf("\n");
    return 0;
}