fork download 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define all(a) (a).begin(), (a).end()
  4. #define dbg_line(x) cout << (x) << '\n'
  5. #define dbg(x) cout << x << " "
  6.  
  7. using namespace std;
  8.  
  9. // <--> Report constants <-->
  10.  
  11. typedef pair<int, int> pii;
  12. const int max_n = 1e6 + 5;
  13. const ll inf = 1e9;
  14. const ll m_inf = -1e9;
  15. const ll mod = 1e9 + 7;
  16. const int base = 32;
  17.  
  18. // <--> Report variables <-->
  19.  
  20. ll pref[max_n];
  21. ll mult[max_n];
  22.  
  23. // <--> Main Code is Here <-->
  24.  
  25. void setIO(){
  26.     ios_base::sync_with_stdio(false);
  27.     cin.tie(NULL);
  28.     cout.tie(NULL);
  29. }
  30.  
  31. void call_file(){
  32.     freopen("input.txt","r",stdin);
  33.     freopen("output.txt","w",stdout);
  34. }
  35.  
  36. void buildHash(string s){
  37.     pref[0] = 0;
  38.     mult[0] = 1;
  39.  
  40.     int n = s.length();
  41.     for (int i = 1; i <= n; i++){
  42.         pref[i] = (pref[i - 1] * base + s[i - 1] - 'a' + 1) % mod;
  43.         mult[i] = (mult[i - 1] * base) % mod;
  44.     }
  45. }
  46.  
  47. ll getHashString(string s){
  48.     ll result = 0;
  49.     for (char c: s){
  50.         result = (result * base + c - 'a' + 1) % mod;
  51.     }
  52.     return result;
  53. }
  54.  
  55. ll getHash(int l, int r){
  56.     return (pref[r] - (pref[l - 1] * mult[r - l + 1]) % mod + mod) % mod;
  57. }
  58.  
  59. int main(){
  60.     setIO();
  61.     call_file();
  62.     int n;
  63.     cin >> n;
  64.     string res = "";
  65.     string t;
  66.     cin >> t;
  67.     res += t;
  68.     string prev = t;
  69.     for (int i = 1; i < n; i++){
  70.         string s;
  71.         cin >> s;
  72.         buildHash(s);
  73.         string tmp = "";
  74.         int right = 0;
  75.         for (int j = prev.size() - 1; j >= 0; j--){
  76.             tmp = prev[j] + tmp;
  77.             int hashTmp = getHashString(tmp);
  78.             if (tmp.size() > s.size()){
  79.                 break;
  80.             }
  81.             if (getHash(1, tmp.size()) == hashTmp){
  82.                 right = tmp.size();
  83.             }
  84.         }
  85.         for (int j = right; j < s.size(); j++){
  86.             res += s[j];
  87.         }
  88.         prev = s;
  89.     }
  90.     cout << res;
  91. }
  92.  
Success #stdin #stdout 0.01s 5924KB
comments (?)
stdin 
Standard input is empty
stdout 
Standard output is empty
https://ideone.com/l5aL6R
language:
C++ (gcc 8.3)
created:
4 days ago
visibility:
public

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!