Pagini recente » Cod sursa (job #467189) | Cod sursa (job #2442676) | Cod sursa (job #1992735) | Cod sursa (job #936414) | Cod sursa (job #2609918)
#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()
{
bool gasit = false;
do{
gasit = false;
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);
gasit = true;
}
}
}while(gasit);
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;
}