?
# | Author | Problem | Lang | Verdict | Time | Memory | Sent | Judged | |
---|---|---|---|---|---|---|---|---|---|
58603158 |
Contestant: JustInCase |
1200E - 47 | C++17 (GCC 7-32) | Accepted | 217 ms | 29336 KB | 2019-08-11 16:40:04 | 2019-08-11 18:25:10 |
#include <bits/stdc++.h> const int32_t MAX_LEN = 1e6; int32_t encode_char(char c) { if(c >= 'a' && c <= 'z') { return c - 'a' + 1; } else if(c >= 'A' && c <= 'Z') { return c - 'A' + 27; } else { return c - '0' + 53; } } struct Hash { const static int32_t BASES[]; const static int32_t MODS[]; static std::vector< int32_t > basePowers[]; static void compute_base_powers() { for(int32_t h = 0; h < 2; h++) { basePowers[h].push_back(1); for(int32_t i = 1; i <= MAX_LEN; i++) { basePowers[h].push_back(((int64_t) basePowers[h].back() * BASES[h]) % MODS[h]); } } } std::vector< int32_t > vals[2]; Hash() {} Hash(const std::string &s) { for(int32_t h = 0; h < 2; h++) { vals[h].push_back(encode_char(s[0])); for(int32_t i = 1; i < s.size(); i++) { vals[h].push_back((vals[h].back() + (int64_t) basePowers[h][i] * encode_char(s[i])) % MODS[h]); } } } void append_char(int32_t encodedChar) { for(int32_t h = 0; h < 2; h++) { int32_t curr = (!vals[h].empty() ? vals[h].back() : 0); vals[h].push_back((curr + (int64_t) basePowers[h][vals[h].size()] * encodedChar) % MODS[h]); } } std::pair< int32_t, int32_t > get_subhash(int32_t low, int32_t high) { int32_t subHash[2]; for(int32_t h = 0; h < 2; h++) { int32_t lh = (low == 0 ? 0 : vals[h][low - 1]); int32_t hh = vals[h][high]; subHash[h] = (hh - lh + MODS[h]) % MODS[h]; } return { subHash[0], subHash[1] }; } }; const int32_t Hash::BASES[] = { 143, 137 }; const int32_t Hash::MODS[] = { (int32_t) 1e9 + 7, (int32_t) 1e9 + 9 }; std::vector< int32_t > Hash::basePowers[2]; Hash h; std::string ansString = ""; void add_word(const std::string &s) { Hash aux = Hash(s); int32_t ans = 0; for(int32_t i = s.size(); i >= 1; i--) { if(i > ansString.size()) { continue; } auto suffHash = h.get_subhash(ansString.size() - i, ansString.size() - 1); auto prefHash = aux.get_subhash(0, i - 1); prefHash.first = ((int64_t) prefHash.first * Hash::basePowers[0][ansString.size() - i]) % Hash::MODS[0]; prefHash.second = ((int64_t) prefHash.second * Hash::basePowers[1][ansString.size() - i]) % Hash::MODS[1]; if(prefHash == suffHash) { ans = i; break; } } for(int32_t i = ans; i < s.size(); i++) { ansString += s[i]; h.append_char(encode_char(s[i])); } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(nullptr); Hash::compute_base_powers(); int32_t n; std::cin >> n; for(int32_t i = 0; i < n; i++) { std::string s; std::cin >> s; add_word(s); } std::cout << ansString << '\n'; }
?
?
?
?