Pagini recente » Cod sursa (job #2102654) | Cod sursa (job #2233060) | Cod sursa (job #1664478) | Cod sursa (job #30485) | Cod sursa (job #2470023)
//wish me luck
#include <bits/stdc++.h>
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
const int NMAX = 30005;
const int LMAX = 20;
vector < string > v;
string s;
int t,pi[NMAX],n,mat[LMAX][LMAX];
int vf[LMAX], st[LMAX];
int ans[LMAX],ansl;
void make_prefix(int i){
int q = 0,j;
pi[1] = 0;
for(j = 2 ; j <= n ; j++){
while(q && v[i][q + 1] != v[i][j])
q = pi[q];
if(v[i][q + 1] == v[i][j])
q++;
pi[j] = q;
}
}
bool is_somewhere(int x){
int j,q,i,m;
for(j = 0 ; j < v.size() ; j++)
if(x != j){
q = 0;
m = v[j].size() - 1;
for(i = 1 ; i <= m ; i++){
while(q && v[x][q + 1] != v[j][i])
q = pi[q];
if(v[x][q + 1] == v[j][i])
q++;
if(q == n)
return 1;
}
}
return 0;
}
int solutie;
void beckateu(int k){
if(k == v.size() + 1){
if(solutie > ansl){
ansl = solutie;
for(int i = 1 ; i < k ; i++)
ans[i] = st[i];
}
return;
}
if(k == 1){
for(int i = 0 ; i < v.size() ; i++){
st[k] = i;
vf[i] = 1;
beckateu(k + 1);
vf[i] = 0;
}
return;
}
for(int i = 0 ; i < v.size() ; i++)
if(!vf[i]){
vf[i] = 1;
solutie += mat[st[k - 1]][i];
st[k] = i;
beckateu(k + 1);
solutie -= mat[st[k - 1]][i];
vf[i] = 0;
}
}
int main(){
int i,j,q,ii,jj,k;
f >> t;
for(i = 1 ; i <= t ; i++){
f >> s;
s = ' ' + s;
v.push_back(s);
s.clear();
}
for(i = 0 ; i < v.size() ; i++){
n = v[i].size() - 1;
make_prefix(i);
if(is_somewhere(i))
v.erase(v.begin() + i);
}
int maxx = 0;
for(i = 0 ; i < v.size() ; i++)
for(j = i + 1 ; j < v.size() ; j++)
if(i != j){
q = 0;
pi[1] = 0;
for(ii = 2 ; ii < v[i].size() ; ii++){
while(q && v[i][ii] != v[j][q + 1])
q = pi[q];
if(v[i][ii] == v[j][q + 1])
q++;
pi[ii] = q;
}
mat[i][j] = q;
q = 0;
pi[1] = 0;
for(jj = 2 ; jj < v[j].size() ; jj++){
while(q && v[j][jj] != v[i][q + 1])
q = pi[q];
if(v[j][jj] == v[i][q + 1])
q++;
pi[jj] = q;
}
mat[j][i] = q;
}
beckateu(1);
g << v[ans[1]];
for(i = 2 ; i <= v.size() ; i++){
for(j = mat[ans[i - 1]][ans[i]] + 1 ; j < v[ans[i]].size() ; j++)
g << v[ans[i]][j];
}
return 0;
}