Cod sursa(job #2609913)

Utilizator victorzarzuZarzu Victor victorzarzu Data 3 mai 2020 19:50:40
Problema ADN Scor 90
Compilator cpp-64 Status done
Runda Arhiva de probleme Marime 2.55 kb
#include <bits/stdc++.h>
#define MAXN (1 << 18)
#define oo 0x3f3f3f3f

using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
int n, minim = oo, poz;
vector<string> text;
int pi[30005];
int C[MAXN + 5][20], Cost[20][20];

void Read()
{
  f>>n;
  string s;
  for(int i = 0;i < n;++i)
    f>>s, text.push_back(s);
  memset(C, oo, sizeof(C));
  f.close();
}

void compute(string cuv)
{
  int q = 0;
  pi[1] = 0;
  for(int i = 2;i <= cuv.length();++i)
    {
      while(q && cuv[q] != cuv[i - 1])
        q = pi[q];
      if(cuv[q] == cuv[i - 1])
        ++q;
      pi[i] = q;
    }
}

int KMP(string cuv1, string cuv2)
{
  int q = 0;
  for(int i = 1;i <= cuv2.length();++i)
    {
      while(q && cuv1[q] != cuv2[i - 1])
        q = pi[q];
      if(cuv1[q] == cuv2[i - 1])
        ++q;
      if(q == cuv1.length() - 1)
        {
            return 0;
        }
    }
  return cuv1.length() - q;
}

void reconstruct(int mask, int varf)
{
  if((mask & (mask - 1)) == 0)
    {
      for(int i = 0;i < n;++i)
        if((1 << i) == mask)
          {
            g<<text[i];
            return;
          }
    }
  int mask2 = mask ^ (1 << varf);
  for(int i = 0;i < n;++i)
    {
      if(C[mask][varf] == C[mask2][i] + Cost[i][varf])
        {
           reconstruct(mask2, i);
           g<<text[varf].substr(text[varf].length() - Cost[i][varf]);
           return;
        }
    }
}

void lant()
{
  for(int mask = 1;mask < (1 << n);++mask)
    for(int pos = 0;pos < n;++pos)
      if(mask & (1 << pos))
        {
          int mask2 = mask ^ (1 << pos);
          if(mask2 == 0)
            {
              C[mask][pos] = text[pos].length();
              break;
            }
          for(int j = 0;j < n;++j)
            if(mask2 & (1 << j))
              C[mask][pos] = min(C[mask][pos], C[mask2][j] + Cost[j][pos]);
        }
  for(int i = 0;i < n;++i)
    if(C[(1 << n) - 1][i] < minim)
      minim = C[(1 << n) - 1][i], poz = i;
  reconstruct((1 << n) - 1, poz);
}

void Solve()
{
  for(int i = 0;i < n;++i)
    {
        compute(text[i]);
        for(int j = 0;j < n;++j)
          if(i != j && !(KMP(text[i], text[j])))
              {
                --n;
                text.erase(text.begin() + i);
              }
    }
  for(int i = 0;i < n;++i)
    {
        compute(text[i]);
        for(int j = 0;j < n;++j)
          if(i != j)
            Cost[j][i] = KMP(text[i], text[j]);
    }
  lant();
  g.close();
}

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