Cod sursa(job #218137)

Utilizator RobytzzaIonescu Robert Marius Robytzza Data 31 octombrie 2008 23:05:06
Problema ADN Scor 30
Compilator cpp Status done
Runda Arhiva de probleme Marime 2.12 kb
#include <fstream>
#include <string>

using namespace std;

ifstream fin ("adn.in");
ofstream fout ("adn.out");

char s[20][30010];
int n;
char rez[60000];
char sol[60000];
int viz[22];
int d[30010];

void pre(char s[])
{
     d[1]=0;
     int k=0,n=strlen(s);
     for (int i=2;i<n;i++)
     {
          while (k && s[k+1]!=s[i])
               k=d[k];
          if (s[k+1]==s[i])
               k++;
          d[i]=k;
     }
}

void kmp(char sol[600000],char s[600000])
{
     int n=strlen(sol);
     int m=strlen(s);
     int k=0;
     for (int i=1;i<n;i++)
     {
          while (k && s[k+1]!=sol[i])
               k=d[k];
          if (s[k+1]==sol[i])
               k++;
          if (k==m)
          {
               return ;
               k=d[k];
          }
     }
     for (int i=k+1;i<m;i++)
          sol[n++]=s[i];
}

void back(int k)
{
     if (k==n)
     {
          if (strlen(rez)==0)
          {
               strcpy(rez,sol);
               return ;
          }
          if (strlen(sol)<strlen(rez))
          {
               memset(rez,0,sizeof(rez));
               strcpy(rez,sol);
          }
          else
               if (strlen(sol)==strlen(rez))
                    if (strcmp(sol,rez)<0)
                    {
                         memset(rez,0,sizeof(rez));
                         strcpy(rez,sol);
                    }
          return ;

     }
     for (int i=1;i<=n;i++)
     if (!viz[i])
     {
          viz[i]=1;
          pre(s[i]);
          char aux[60000];
          aux[0]=0;
          strcpy(aux,sol);
          kmp(sol,s[i]);
          back(k+1);
          viz[i]=0;
          memset(sol,0,sizeof(sol));
          strcpy(sol,aux);
     }
}

void citire()
{
     fin>>n;
     char c;
     int nr;
     fin.get(c);
     for (int i=1;i<=n;i++)
     {
          s[i][0]='-';
          nr=1;
          fin.get(c);
          while (c!='\n')
          {
               s[i][nr++]=c;
               fin.get(c);
          }
     }
}

int main ()
{
     citire();
     back(0);
     fout<<rez;
     return 0;
}