Cod sursa(job #1586855)

Utilizator SilviuIIon Silviu SilviuI Data 1 februarie 2016 18:01:34
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.48 kb
#include <stdio.h>
#include <string>
#include <vector>
#include <iostream>
#define lmax 30010

using namespace std;

int n,st,nr;
int dp[20][lmax*10],path[20][lmax*10];
int urm[lmax],dif[20][20],sol[20];
bool del[20],viz[20][lmax*10];
string s[20];
char ss[lmax];
vector < pair<int,int> > g[20];

int memo(int nod,int mask)
{
    if (mask==0) return 0; else
    if (viz[nod][mask]) return dp[nod][mask];
    viz[nod][mask]=true;
    for (unsigned int i=0;i<g[nod].size();i++) {
        int y=g[nod][i].first;
        if (y==st && mask==1<<y) continue;
        if (((mask>>(y-1))&1)==1) {
            int val=memo(y,mask-(1<<(y-1)))+g[nod][i].second;
            if (dp[nod][mask]<val) {
                dp[nod][mask]=val; path[nod][mask]=y;
            }
        }
    }
    return dp[nod][mask];
}

void findpath(int nod,int mask)
{
    if (mask==0) return; else
    {
        int x=path[nod][mask];
        nr++; sol[nr]=x;
        findpath(x,mask-(1<<(x-1)));
    }
}

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

    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        scanf("%s",ss); s[i]=ss; s[i].insert(0," ");
    }

    for (int i=1;i<=n;i++)
        if (!del[i]) {
            for (int j=1;j<=n;j++)
                if (i!=j && !del[j]) {
                    urm[1]=0; int k=0;
                    for (int l=2;l<(int)s[i].size();l++) {
                        while (k>0 && s[i][l]!=s[i][k+1]) k=urm[k];
                        if (s[i][l]==s[i][k+1]) k++;
                        urm[l]=k;
                    }

                    bool ok=false; k=0;
                    for (int l=1;l<(int)s[j].size();l++) {
                        while (k>0 && s[j][l]!=s[i][k+1]) k=urm[k];
                        if (s[j][l]==s[i][k+1]) k++;
                        if (k==s[i].size()-1) { ok=true; break; }
                    }

                    if (ok) { del[i]=true; break; }
                }
    }

    int m=0;
    for (int i=1;i<=n;i++)
        if (!del[i]) { m++; s[m]=s[i]; }

    n=m;

    for (int i=1;i<=n;i++) {
        for (int j=1;j<=n;j++)
        if (i!=j) {
            /*verific daca prefixul lui s[i] se regaseste ca sufix in s[j]; */
            urm[1]=0; int k=0;
            for (int l=2;l<(int)s[i].size();l++) {
                while (k>0 && s[i][l]!=s[i][k+1]) k=urm[k];
                if (s[i][l]==s[i][k+1]) k++;
                urm[l]=k;
            }

            k=0;
            for (int l=1;l<(int)s[j].size();l++) {
                while (k>0 && s[j][l]!=s[i][k+1]) k=urm[k];
                if (s[j][l]==s[i][k+1]) k++;
                if (k==s[i].size()-1) k=urm[k];
            }

            g[i].push_back(make_pair(j,k)); dif[i][j]=k;
        }
    }

    for (int i=1;i<=n;i++) s[i].erase(s[i].begin());

    int maxx=(1<<n)-1;
    for (int i=1;i<=1;i++) {
        st=i;
        for (int j=1;j<=n;j++)
            for (int k=1;k<=maxx;k++)
                dp[j][k]=0,viz[j][k]=false;

        for (int j=0;j<g[i].size();j++) {
            int val=memo(g[i][j].first,maxx-(1<<(g[i][j].first-1))+g[i][j].second);
            if (dp[i][maxx]<val) {
                dp[i][maxx]=val; path[i][maxx]=g[i][j].first;
            }
        }
    }

    nr=1; sol[nr]=1;
    findpath(1,maxx);

    for (int i=nr;i>1;i--) {
        int y=dif[sol[i-1]][sol[i]];
        for (int j=0;j<s[sol[i-1]].size()-y;j++) printf("%c",s[sol[i]][j]);
    }

    return 0;
}