Cod sursa(job #1071222)

Utilizator andrettiAndretti Naiden andretti Data 2 ianuarie 2014 19:10:07
Problema ADN Scor 100
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.81 kb
#include<stdio.h>
#include<algorithm>
#include<cstring>
#define maxn 20
#define maxl 30005
#define maxm 1<<18
#define inf 0x3f3f3f3f
using namespace std;

int n,nr,sol,E;
int len[maxn],p[maxl],used[maxn];
int c[maxn][maxn],d[maxn][maxn],node[maxn],rnode[maxn];
int s[maxm][maxn],father[maxm][maxn];
char a[maxn][maxl];

void read()
{
    scanf("%d\n",&n);
    for(int i=1;i<=n;i++)
    {
        scanf("%s\n",a[i]+1);
        len[i]=strlen(a[i]+1);
    }
}

int kmp(int x,int y)
{
    int k=0;
    memset(p,0,sizeof(p));
    p[1]=0;
    for(int i=2;i<=len[x];i++)
    {
        while(k && a[x][k+1]!=a[x][i]) k=p[k];
        if(a[x][k+1]==a[x][i]) k++;
        p[i]=k;
    }

    k=0;
    for(int i=1;i<=len[y];i++)
    {
        while(k && a[x][k+1]!=a[y][i]) k=p[k];
        if(a[x][k+1]==a[y][i]) k++;
        if(k==len[x]) {used[x]=1; return -1;}
    }
    return k;
}

void init()
{
    for(int i=1;i<=nr;i++)
     for(int j=1;j<=nr;j++)
      d[i][j]=0;
}

void build_graph()
{
    int x,y;
    for(int i=1;i<n;i++) if(!used[i])
     for(int j=i+1;j<=n;j++) if(!used[j])
     {
         x=kmp(i,j); if(x==-1) break;
         y=kmp(j,i); c[i][j]=y; c[j][i]=x;
     }

    for(int i=1;i<=n;i++) if(!used[i])
      node[i]=++nr,rnode[nr]=i;

    init();
    for(int i=1;i<n;i++) if(!used[i])
     for(int j=i+1;j<=n;j++) if(!used[j])
     {
         d[node[i]][node[j]]=c[i][j];
         d[node[j]][node[i]]=c[j][i];
     }
}

void det(int mask,int k)
{
    int newm;

    s[mask][k]=inf;
    for(int i=0;(mask>>i);i++)
     if( ((mask>>i)&1) )
     {
         newm=mask^(1<<(k-1));
         if(s[newm][i+1]==-1) det(newm,i+1);
         if(s[mask][k]>s[newm][i+1]+len[rnode[k]]-d[i+1][k])
         {
             s[mask][k]=s[newm][i+1]+len[rnode[k]]-d[i+1][k];
             father[mask][k]=i+1;
         }
     }
}

void init_s()
{
    for(int i=1;i<(1<<nr);i++)
     for(int j=1;j<=nr;j++)
      s[i][j]=-1;
    for(int i=1;i<=nr;i++) s[1<<(i-1)][i]=len[rnode[i]];
    memset(father,0,sizeof(father));
}

void solve()
{
    sol=inf;
    init_s();
    for(int j=1;j<=nr;j++)
    {
        det((1<<nr)-1,j);
        if(s[(1<<nr)-1][j]<sol)
        {
            sol=s[(1<<nr)-1][j]; E=j;
        }
    }
}

void print(int m,int k)
{
    int newm;
    if(!father[m][k])
    {
        for(int i=1;i<=len[rnode[k]];i++)
         printf("%c",a[rnode[k]][i]);
        return;
    }
    newm=m^(1<<(k-1));
    print(newm,father[m][k]);
    for(int i=d[father[m][k]][k]+1;i<=len[rnode[k]];i++)
     printf("%c",a[rnode[k]][i]);
}

int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);

    read();
    build_graph();
    solve();
    print((1<<nr)-1,E);

    fclose(stdin);
    fclose(stdout);
    return 0;
}