Cod sursa(job #57344)

Utilizator raula_sanChis Raoul raula_san Data 1 mai 2007 20:07:28
Problema ADN Scor 0
Compilator cpp Status done
Runda Arhiva de probleme Marime 3.27 kb
#include <stdio.h>
#include <string.h>

#define Ldim 30001
#define Ndim 19

int  Next[Ndim][Ldim], A[Ndim][Ndim], S[Ndim], Sol[Ndim], Config[Ndim], Uz[Ndim], D[Ndim][Ndim], Tata[Ndim][Ndim];
int  N, M, X, Cmax;
char T[Ndim][Ldim];

void Read();
void Solve();
void Print();

void Prefix(char *, int *);
void Back(int);

int Potrivire(char *, char *, int *);

int main()
{
    Read();
    Solve();
	Print();
    
    return 0;
}

void Read()
{
     freopen("adn.in", "r", stdin);
     
     int i;
     for(scanf("%d\n", &N), i=1; i<=N; ++i)
     {
         scanf("%s", &T[i]);              
		 Prefix(T[i], Next[i]);
         S[i] = 1;
     }

     fclose(stdin);
}

void Solve()
{
     int i, j, k, p;
     
     for(i=1; i<=N; ++i)
			  for(j=1; j<=N; ++j)
					   if(i != j && S[i] && S[j])
                       {
							A[i][j] = Potrivire(T[i], T[j], Next[j]);

							if(A[i][j] == -1) S[j] = 0;
					   }

    for(i=1; i<=N; ++i) X += S[i];

//    Back(1);
    
    for(i=2; i<=X; ++i)
    {
             for(j=1; j<=N; ++j)
                      if(S[j])
                      {
                              for(k=1; k<=N; ++k)
                                       if(S[k] && k != j && D[i-1][k] + A[k][j] > D[i][j])
                                       {
                                            D[i][j] = D[i-1][k] + A[k][j];
                                            Tata[i][j] = k;
                                       }
                      }
    }    

    for(i=1; i<=N; ++i)
             if(S[i] && D[X][i] > Cmax)
             {
                     Cmax = D[X][i];
                     p = i;
             }

	i = X;
	while(i)
	{
			Config[i] = p;
			p = Tata[i][p];
			-- i;
	}
}

void Print()
{
     freopen("adn.out", "w", stdout);

	 printf("%s", T[Config[1]]);

	 int i, j, n;

	 for(i=2; i<=X; ++i)
	 {
        n = strlen(T[Config[i]]);

		for(j=A[Config[i-1]][Config[i]]-1; j<n; ++j)
			printf("%c", T[Config[i]][j]);
	 }

	 fclose(stdout);
}

void Prefix(char *T, int *Next)
{
     int n = strlen(T), q, k;
     
	 for(q=2, k=0; q<n; ++q)
	 {
			  while(k > 0 && T[k] != T[q]) k = Next[k];

			  if(T[k] == T[q]) ++ k;
              
              Next[q] = k;
     }
}

void Back(int k)
{
     if(k == X + 1)
     {
          int i, cost = 0;
          
          for(i=1; i<X; ++i)
                   cost += A[Sol[i]][Sol[i+1]];
          
		  if(cost >= Cmax)
          {
                  Cmax = cost;
                  for(i=1; i<=X; ++i) Config[i] = Sol[i];
          }
     }
     
     else
     {
         int i;
         for(i=1; i<=N; ++i)
                  if(S[i] && !Uz[i])
                  {
                          Sol[k] = i;
                          Uz[i] = 1;
                          Back(k + 1);
                          Uz[i] = 0;
                  }
     }
}

int Potrivire(char *T, char *P, int *Next)
{
    int C[Ldim] = { 0 };
    int q, k, n, m;
    
    n = strlen(T);
    m = strlen(P);
    
	for(q=0, k=0; q<n; ++q)
	{
			 while(k > 0 && P[k] != T[q])
					 k = Next[k];

			 if(P[k] == T[q]) ++ k;

			 C[q] = k;

			 if(k == m)
                  return -1;
    }
    
	return C[n-1] + 1;
}