Pagini recente » Cod sursa (job #2906063) | Cod sursa (job #85987) | Cod sursa (job #2002865) | Cod sursa (job #2210177) | Cod sursa (job #2285700)
#include <iostream>
#include <fstream>
#include <algorithm>
#include <vector>
#include <string>
#include <cstring>
using namespace std;
ifstream in("adn.in");
ofstream out("adn.out");
inline bool isincluded(string needle, string haystack) {
vector<int> pi(needle.size(), 0);
int k = 0;
for(int i = 2; i < needle.size(); i ++) {
while(k > 0 && needle[i] != needle[k + 1])
k = pi[k];
if(needle[k + 1] == needle[i])
k ++;
pi[i] = k;
}
k = 0;
for(int i = 1; i < haystack.size(); i ++) {
while(k > 0 && haystack[i] != needle[k + 1])
k = pi[k];
if(haystack[i] == needle[k + 1])
k ++;
if(k == needle.size() - 1)
return 1;
}
return 0;
}
inline int computekmp(string l, string r) {
string s = l + r;
vector<int> pi(s.size(), 0);
int k = 0;
for(int i = 2; i < s.size(); i ++) {
while(k > 0 && s[i] != s[k + 1])
k = pi[k];
if(s[i] == s[k + 1])
k ++;
pi[i] = k;
}
return pi[s.size() - 1];
}
int main() {
int n;
in >> n;
vector<string> v(n + 1);
for(int i = 1; i <= n; i ++) {
in >> v[i];
v[i] = " " + v[i];
}
vector<string> words;
for(int i = 1; i <= n; i ++) {
bool flag = 0;
for(int j = 1; j <= n; j ++)
if(i != j && isincluded(v[i], v[j])) {
flag = 1;
break;
}
if(!flag)
words.push_back(v[i]);
}
//trag muchii
n = words.size();
vector<vector<int> > cost(n, vector<int> (n, -1));
for(int i = 0; i < n; i ++)
for(int j = 0; j < n; j ++)
if(i != j)
cost[j][i] = computekmp(words[i], words[j]);
//caut lantul hamiltonian de cost maxim
int mx = -1, x, y;
for(int start = 0; start < n; start ++) {
vector<vector<int> > dp((1 << n), vector<int> (n, -1));
dp[1 << start][start] = 0;
for(int mask = 1; mask < (1 << n); mask ++)
for(int i = 0; i < n; i ++)
if(mask & (1 << i) && dp[mask][i] != -1)
for(int j = 0; j < n; j ++)
if((mask & (1 << j)) == 0)
dp[mask ^ (1 << j)][j] = max(dp[mask ^ (1 << j)][j], dp[mask][i] + cost[i][j]);
for(int i = 0; i < n; i ++) {
if(mx < dp[(1 << n) - 1][i]) {
x = start;
y = i;
mx = dp[(1 << n) - 1][i];
}
}
}
vector<vector<int> > rdp((1 << n), vector<int> (n, -1));
vector<vector<int> > from((1 << n), vector<int> (n, -1));
int start = x;
rdp[1 << start][start] = 0;
for(int mask = 1; mask < (1 << n); mask ++)
for(int i = 0; i < n; i ++)
if(mask & (1 << i) && rdp[mask][i] != -1)
for(int j = 0; j < n; j ++)
if((mask & (1 << j)) == 0)
if(rdp[mask ^ (1 << j)][j] < rdp[mask][i] + cost[i][j]) {
rdp[mask ^ (1 << j)][j] = rdp[mask][i] + cost[i][j];
from[mask ^ (1 << j)][j] = i;
}
int node = y, nr = n - 1, mask = (1 << n) - 1;
vector<int> ans(n, 0);
while(node != -1) {
ans[nr --] = node;
int cnode = node;
node = from[mask][node];
mask ^= (1 << cnode);
}
int toskip = 1;
for(int i = 0; i < n; i ++) {
for(int j = toskip; j < words[ans[i]].size(); j ++)
out << words[ans[i]][j];
if(i + 1 < n)
toskip = cost[ans[i]][ans[i + 1]] + 1;
}
return 0;
}