Pagini recente » Cod sursa (job #255546) | Cod sursa (job #1483897) | Cod sursa (job #2868654) | Cod sursa (job #1513332) | Cod sursa (job #3295900)
#include <fstream>
#include <vector>
#include <algorithm>
using ll = long long;
constexpr int INF = 1e9;
constexpr int MOD = 1e9 + 9;
struct ZP {
int x;
constexpr ZP( int x = 0 ): x(x % MOD) {}
ZP( ll x ): x(x % MOD) {}
bool operator == ( const ZP& that ) const { return x == that.x; }
ZP operator *= ( const ZP& that ) { return *this = ZP(x * (ll)that.x); }
ZP operator += ( const ZP& that ) {
x += that.x;
if( x >= MOD )
x -= MOD;
return *this;
}
ZP operator -= ( const ZP& that ) {
x += MOD - that.x;
if( x >= MOD )
x -= MOD;
return *this;
}
ZP operator * ( const ZP& that ) const { return ZP(*this) *= that; }
ZP operator + ( const ZP& that ) const { return ZP(*this) += that; }
ZP operator - ( const ZP& that ) const { return ZP(*this) -= that; }
};
constexpr ZP BASE = 17;
constexpr ZP IBASE = int((1e9 + 10) / 17);
ZP pibase( int n ) {
static std::vector<ZP> vals(1, 1);
for( int i = vals.size(); i <= n; i++ )
vals.push_back( vals.back() * IBASE );
return vals[n];
}
struct Axel {
std::vector<int> str;
std::vector<ZP> sp;
Axel() = default;
Axel( const std::string &_str ): str(_str.begin(), _str.end()), sp(str.size() + 1, 0) {
ZP pb = 1;
for( int i = 0; i < (int)str.size(); i++ ){
sp[i + 1] = sp[i] + pb * ZP(str[i]);
pb *= BASE;
}
}
int size() const { return (int)str.size(); }
ZP hash( int st, int dr ) const { return pibase( st ) * (sp[dr + 1] - sp[st]); }
};
std::ifstream fin("adn.in");
std::ofstream fout("adn.out");
int main() {
int n;
fin >> n;
std::vector<Axel> words;
for( int i = 0; i < n; i++ ){
std::string str;
fin >> str;
words.emplace_back( str );
}
{// first, check for full overlap, remove useless
std::vector<bool> good(n, true);
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ ){
if( (int)words[i].size() >= (int)words[j].size() )
continue;
bool shit = false;
ZP wi = words[i].hash( 0, (int)words[i].size() - 1 );
for( int delta = 0; delta + (int)words[i].size() - 1 < (int)words[j].size(); delta++ )
shit |= (wi == words[j].hash( delta, delta + (int)words[i].size() - 1 ));
if( shit )
good[i] = false;
}
int sp = 0;
for( int i = 0; i < n; i++ )
if( good[i] )
words[sp++] = words[i];
words.resize( n = sp );
}
// now try sticking shit together
std::vector<std::vector<int>> adj(n, std::vector<int>(n));
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ ){
int maxlen = std::min( (int)words[i].size(), (int)words[j].size() );
for( int len = 0; len <= maxlen; len++ )
if( words[i].hash( (int)words[i].size() - len, (int)words[i].size() - 1 ) == words[j].hash( 0, len - 1 ) )
adj[i][j] = (int)words[j].size() - len;
}
// now stick everything together
int p2 = (1 << n);
std::vector<std::vector<int>> minlen(p2, std::vector<int>(n, +INF));
std::vector<std::vector<int>> prev(p2, std::vector<int>(n));
for( int i = 0; i < n; i++ )
minlen[1 << i][i] = (int)words[i].size();
for( int mask = 0; mask < p2; mask++ )
for( int i = 0; i < n; i++ )
for( int j = 0; j < n; j++ ){
int aux = minlen[mask][i] + adj[i][j];
int nmask = (mask | (1 << j));
if( aux < minlen[nmask][j] ){
minlen[nmask][j] = aux;
prev[nmask][j] = i;
}
}
std::vector<int> sol; {
int mask = p2 - 1, u = 0;
for( int i = 0; i < n; i++ )
if( minlen[mask][i] < minlen[mask][u] )
u = i;
while( mask ){
sol.push_back( u );
int next = prev[mask][u];
mask -= (1 << u);
u = next;
}
std::reverse( sol.begin(), sol.end() );
}
std::string ret(words[sol[0]].str.begin(), words[sol[0]].str.end());
for( int i = 1; i < n; i++ ){
int a = sol[i - 1], b = sol[i];
ret.insert( ret.end(), words[b].str.end() - adj[a][b], words[b].str.end() );
}
fout << ret << std::endl;
return 0;
}