Cod sursa(job #1009792)

Utilizator dobrebogdanDobre Bogdan Mihai dobrebogdan Data 13 octombrie 2013 20:52:10
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.06 kb
#include<stdio.h>
#include<math.h>
#include<string.h>
int pr[30][30],pi[30][30],l[30],d[265000][23],p[30],xu[265000][23],yu[265000][23];
char a[23][30005],s[550000];
bool t[30];
int main()
{
    freopen("adn.in","r",stdin);
    freopen("adn.out","w",stdout);
   int n,i,x,j,q,m=1,y,z,w,lg,u,sn;
    scanf("%d\n",&n);
    p[0]=1;
    for(i=1;i<=n;i++)
    {p[i]=p[i-1]*2;
        gets(a[i]+1);
        l[i]=strlen(a[i]+1);
    pi[i][1]=x=0;
for(j=2;j<=l[i];j++)
{
    while(a[i][x+1]!=a[i][j] && x>0)
        {
x=pi[i][x];
        }
        if(a[i][x+1]==a[i][j])
        x++;
        pi[i][j]=x;
}
    }
    for(i=1;i<=n;i++)
        for(j=1;j<=n;j++)
        if(j!=i)
    {
        x=0;
for(q=1;q<=l[j];q++)
{
    while(a[i][x+1]!=a[j][q] && x>0)
    {
        x=pi[i][x];
    }
    if(a[i][x+1]==a[j][q])
        x++;
        if(x==l[i])
            break;
}
if(q!=l[j]+1)
{
    t[i]=1;
    break;
}
pr[i][j]=x;
    }
        for(i=1;i<=n;i++)
        if(t[i]==1)
    {m=m/2;
        for(j=i+1;j<=n;j++)
      {
          l[j-1]=l[j];
          t[j-1]=t[j];
          strcpy(a[j-1]+1,a[j]+1);
          for(q=1;q<=l[j];q++)
            pr[j-1][q-1]=pr[j][q];
      }
      n--;
      i--;
    }
    //no' deci pana aici e bine
m=p[n]-1;
for(i=1;i<=m;i++)
{
    w=i;
        while(w!=0)
        {
            lg=log2(w & (-w))+1;
            x=i-(w & (-w));
            w=w-(w & (-w));
        y=z=0;
        for(q=1;q<=n;q++)
            if(d[x][q]!=0)
        if((d[x][q]-pr[lg][q]<y || y==0))
        {
            y=d[x][q];
        z=q;
        }
        xu[i][lg]=x;
        yu[i][lg]=z;
        d[i][lg]=y+l[lg]-pr[lg][z];
        }
}
w=d[m][1];
for(i=2;i<=n;i++)
    if(d[m][i]<w)
    {
        w=d[m][i];
        j=i;
    }
    x=m;
    y=j;
    sn=0;
    while(x!=0 && y!=0)
    {
    for(i=l[y];i>=1;i--)
    {
    sn++;
        s[sn]=a[y][i];
    }
    j=xu[x][y];
    y=yu[x][y];
    x=j;
    }
    for(i=sn;i>=1;i--)
        printf("%c",s[i]);
    printf("\n");
    return 0;
}