Pagini recente » Cod sursa (job #2227311) | Cod sursa (job #1861062) | Cod sursa (job #1677203) | Cod sursa (job #1733323) | Cod sursa (job #2155211)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <string.h>
#include <vector>
using namespace std;
int N;
int automaton[30005];
const int oo = 2e9;
int d[262150][20];
int prv[262150][20];
string S[20];
string ans;
int cost[20][20];
vector <string> S2;
ifstream in ("adn.in");
ofstream out ("adn.out");
void afis(int sz)
{
for(int i = 0; i < sz; ++i)
cout<<automaton[i]<<" ";
cout<<"\n";
}
void afis2(int conf, int x)
{
//cout<<conf<<", "<<x<<"\n";
if (conf == (1<<x))
{
ans+=S2[x];
//cout<<"SIR CONSTRUIT MOMENTAN CU "<<x<<" ("<<ans<<") "<<"\n";
}
else
{
afis2(conf ^ (1 << x), prv[conf][x]);
for(int i = cost[x][prv[conf][x]]; i < S2[x].size(); ++i)
ans+=S2[x][i];
//cout<<"SIR CONSTRUIT MOMENTAN CU "<<x<<" ("<<ans<<") "<<"\n";
}
}
void kmp_fail(string s)
{
memset(automaton, 0, sizeof(automaton)); //resetam automatul finit
automaton[0] = 0;
int j = 0;
for (int i = 1; i < s.size(); ++i)
{
while(s[i] != s[j] && j > 0)
j = automaton[j - 1];
if(s[i] == s[j])
++j;
automaton[i] = j;
}
}
vector <string> prune () //caut pe i in j
{
vector<string> ret;
for(int i = 0; i < N; ++i)
{
kmp_fail(S[i]); //generam automatul pentru sirul S[i]
bool gasit = false;
for(int j = 0; j < N; ++j)
{
if(i == j) continue;
//cout<<"Caut sirul \""<<S[i]<<"\" in sirul \""<<S[j]<<"\n";
//cout<<"Automatul pt sirul cautat este: "; afis(S[i].size());
int m = 0;
int k = 0;
while(k + m < S[j].size())
{
if(S[i][k] == S[j][k + m])
{
if(k == S[i].size() - 1)
{
gasit = 1;
break;
}
++k;
}
else
{
if(k>0)
{
m += k - automaton[k - 1];
k = automaton[k - 1];
}
else
++m;
}
}
if(gasit)
break;
}
if(!gasit)
ret.push_back(S[i]);
}
return ret;
}
int potrivire(string a, string b)
{
kmp_fail(a);
int m = 0;
int k = 0;
while(k + m < b.size())
{
if(a[k] == b[k + m])
++k;
else
{
if(k>0)
{
m += k - automaton[k - 1];
k = automaton[k - 1];
}
else
++m;
}
}
return k;
}
int main()
{
in>>N;
for(int i = 0; i < N; ++i)
in>>S[i];
S2 = prune();
N = S2.size();
for(int i = 0; i < N; ++i)
for(int j = 0; j < N; ++j)
{
if(i == j)
continue;
cost[i][j] = potrivire(S2[i], S2[j]); //j - i
//cout<<"Sirul "<<j<<" ("<<S2[j]<<") se potriveste "<<cost[i][j]<<" caractere peste sirul "<<i<<" ("<<S2[i]<<")\n";
}
/*cout<<"\nSirurile care nu sunt continute sunt: \n";
for(int i = 0; i < N; ++i)
cout<<S2[i]<<"\n";*/
//urmeaza dinamica
for(int i = 0; i < (1<<N); ++i)
for(int j = 0; j < N; ++j)
d[i][j] = oo;
for(int i = 0; i < N; ++i)
d[(1<<i)][i] = S2[i].size();
//cout<<"INIT OK!\n";
for(int i = 0; i < (1<<N); ++i)
for(int j = 0; j < N; ++j)
{
if(!(i & (1<<j)) || i == (1<<j))
continue;
for(int k = 0; k < N; ++k)
{
if(!(i & (1<<k)) || j == k)
continue;
if(d[i][j] > d[i ^ (1<<j)][k] + S2[j].size() - cost[j][k])
{
d[i][j] = d[i ^ (1<<j)][k] + S2[j].size() - cost[j][k];
prv[i][j] = k;
}
}
}
//cout<<"DINAMICA OK!\n";
int best = 0;
int i = ((1 << N) - 1);
for (int j = 0; j < N; ++j)
if (d[i][j] < d[i][best])
best = j;
//cout<<best<<"\n";
afis2(i, best);
out<<ans;
}