Pagini recente » Cod sursa (job #2573946) | Cod sursa (job #276218) | Cod sursa (job #1699614) | Cod sursa (job #1373591) | Cod sursa (job #2471292)
// i hope this works
#include <bits/stdc++.h>
using namespace std;
ifstream f("adn.in");
ofstream g("adn.out");
const int inf = 1e9;
const int NMAX = 20;
const int LMAX = 30005;
vector < string > v;
string s;
int n,pi[NMAX][LMAX],m,mat[NMAX][NMAX];
bool is[NMAX];
int dp[NMAX][1 << NMAX], best[NMAX][1 << NMAX], ord[NMAX];
void make_prefix(int i){
int q = 0,j;
pi[i][1] = 0;
for(j = 2 ; j <= m ; j++){
while(q && v[i][q + 1] != v[i][j])
q = pi[i][q];
if(v[i][q + 1] == v[i][j])
q++;
pi[i][j] = q;
}
}
int superposition(int i, int j){
int m = v[i].size() - 1;
int n = v[j].size() - 1;
int q = 0;
for(int ii = 1 ; ii <= m ; ii++){
while(q > 0 && v[j][q + 1] != v[i][ii])
q = pi[j][q];
if(v[j][q + 1] == v[i][ii])
q++;
if(q == n)
return inf;
}
return n - q;
}
bool is_somewhere(int i){
int q,j,jj;
for(jj = 0 ; jj < n ; jj++)
if(jj != i){
q = 0;
m = v[j].size() - 1;
for(j = 1 ; j <= m ; j++){
while(q && v[i][q + 1] != v[jj][j])
q = pi[i][q];
if(v[i][q + 1] == v[jj][j])
q++;
if(q == v[i].size() - 1)
return 1;
}
}
return 0;
}
int main(){
int i,j,ii,q;
f >> n;
for(i = 1 ; i <= n ; i++){
f >> s;
v.push_back(' ' + s);
is[i - 1] = 1;
}
for(i = 0 ; i < n ; i++){
m = v[i].size() - 1;
make_prefix(i);
}
int all = (1 << n) - 1;
int nr = n;
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < n ; j++)
if(i != j && (all & (1 << j))){
mat[i][j] = superposition(i,j);
if(mat[i][j] == inf){
all ^= (1 << j);
nr--;
}
}
for(i = 0 ; i < n ; i++)
for(j = 0 ; j < (1 << n) ; j++)
dp[i][j] = inf;
for(i = 0 ; i < n ; i++)
dp[i][1 << i] = v[i].size() - 1;
for(i = 1 ; i <= all ; i++)
for(j = 0 ; j < n ; j++)
if( (i & (1 << j)) && (all & (1 << j)))
for(ii = 0 ; ii < n ; ii++)
if( !(i & (1 << ii)) && (all & (1 << ii)) && dp[ii][i ^ (1 << ii)] > dp[j][i] + mat[j][ii]){
dp[ii][i ^ (1 << ii)] = dp[j][i] + mat[j][ii];
best[ii][i ^ (1 << ii)] = j;
}
int minim = inf;
int pos = 0;
for(i = 0 ; i < n ; i++)
if((all & (1 << i)) && dp[i][all] < minim){
minim = dp[i][all];
pos = i;
}
//g << minim
int poz = nr, cnr = all;
ord[poz--] = pos;
for(i = 2 ; i <= nr ; i++){
int aux = pos;
pos = best[pos][cnr];
cnr ^= (1 << aux);
ord[poz--] = pos;
}
//for(i = 1 ; i <= nr ; i++)
//g << ord[i] << " ";
for(i = 0 ; i < n ; i++)
v[i].erase(v[i].begin());
g << v[ord[1]];
for(i = 2 ; i <= nr ; i++){
for(j = v[ord[i]].size() - mat[ord[i - 1]][ord[i]] ; j < v[ord[i]].size() ; j++)
g << v[ord[i]][j];
}
return 0;
}