1200E - Compress Words - CodeForces Solution

// Problem: E. Compress Words
// Contest: Codeforces - Codeforces Round 578 (Div. 2)
// URL: https://codeforces.com/contest/1200/problem/E
// Memory Limit: 256 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

// #pragma GCC optimize("-fdelete-null-pointer-checks,inline-functions-called-once,-fexpensive-optimizations,-foptimize-sibling-calls,-ftree-switch-conversion,-finline-small-functions,inline-small-functions,-frerun-cse-after-loop,-fhoist-adjacent-loads,-findirect-inlining,-freorder-functions,no-stack-protector,-fpartial-inlining,-fsched-interblock,-fcse-follow-jumps,-falign-functions,-fstrict-aliasing,-fschedule-insns2,-ftree-tail-merge,inline-functions,-fschedule-insns,-freorder-blocks,-funroll-loops,-fthread-jumps,-fcrossjumping,-fcaller-saves,-fdevirtualize,-falign-labels,-falign-loops,-falign-jumps,unroll-loops,-fsched-spec,-ffast-math,Ofast,inline,-fgcse,-fgcse-lm,-fipa-sra,-ftree-pre,-ftree-vrp,-fpeephole2",3,2)
#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<bits/stdc++.h>
#include<ext/pb_ds/assoc_container.hpp>
#include<ext/pb_ds/hash_policy.hpp>
using namespace __gnu_pbds;
using namespace std;
using i64=long long;
// #define int long long
#define ull unsigned long long
#define PII pair<int,int>
#define eps 1e-7
#define puts(res) cout<<res<<'\n'
#define put cout<<'\n'
#define cout(a) cout<<a<<'\n';
#define debug(a) cout<<#a<<"="<<a<<endl
#define debug2(a,b) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<endl
#define debug3(a,b,c) cout<<#a<<"="<<a<<" "<<#b<<"="<<b<<" "<<#c<<"="<<c<<endl
#define mem1(a) memset(a,-1,sizeof(a))
#define mem0(a) memset(a,0,sizeof(a))
#define mem(a) memset(a,0x3f,sizeof(a))
#define fup(o,a,b) for(int o=a;o<=b;o++)
#define up(a,b) for(int o=a;o<=b;o++)
#define dn(a,b) for(int o=a;o>=b;o--)
#define fdn(o,a,b) for(int o=a;o>=b;o--)
#define show(a) for(auto it:a)cout<<it<<" ";
#define cvec(a) for(auto &it:a)cin>>it;
#define sz(v) (int)v.size()
#define all(a) (a).begin(),(a).end()
#define range(a,n) a+1,a+1+n
#define crange(a,n) up(1,n)cin>>a[o]
#define showcase(a,n) up(1,n)cout<<a[o]<<" \n"[o==n];
#define rall(x) (x).rbegin(), (x).rend()
#define YES {puts("YES");return;}
#define NO {puts("NO");return;}
#define IOS ios::sync_with_stdio(false);cin.tie(0),cout.tie(0)
#define ls(x) (tr[x].l)
#define rs(x) (tr[x].r)
#define sum(x) tr[x].sum
#define endl '\n'
#define fi first
#define se second
#define pb emplace_back
#define pob pop_back
#define pof pop_front
#define pf emplace_front
#define db double
#define MAX 0x7ffffffffffffffff
#define INF 0x3f3f3f3f3f3f3f3f
const int N=2e5+10;
// int n,m;
const int L = 1e6 + 5;
const int HASH_CNT = 2;

int hashBase[HASH_CNT] = {29, 31};
int hashMod[HASH_CNT] = {int(1e9 + 9), 998244353};

struct StringWithHash {
  char s[L];
  int ls;
  int hsh[HASH_CNT][L];
  int pwMod[HASH_CNT][L];

  void init() {  // 初始化
    ls = 0;
    for (int i = 0; i < HASH_CNT; ++i) {
      hsh[i][0] = 0;
      pwMod[i][0] = 1;
    }
  }

  StringWithHash() { init(); }

  void extend(char c) {
    s[++ls] = c;                          // 记录字符数和每一个字符
    for (int i = 0; i < HASH_CNT; ++i) {  // 双哈希的预处理
      pwMod[i][ls] =
          1ll * pwMod[i][ls - 1] * hashBase[i] % hashMod[i];  // 得到b^ls
      hsh[i][ls] = (1ll * hsh[i][ls - 1] * hashBase[i] + c) % hashMod[i];
    }
  }

  vector<int> getHash(int l, int r) {  // 得到哈希值
    vector<int> res(HASH_CNT, 0);
    for (int i = 0; i < HASH_CNT; ++i) {
      int t =
          (hsh[i][r] - 1ll * hsh[i][l - 1] * pwMod[i][r - l + 1]) % hashMod[i];
      t = (t + hashMod[i]) % hashMod[i];
      res[i] = t;
    }
    return res;
  }
};

bool equal(const vector<int> &h1, const vector<int> &h2) {
  assert(h1.size() == h2.size());
  for (unsigned i = 0; i < h1.size(); i++)
    if (h1[i] != h2[i]) return false;
  return true;
}

int n;
StringWithHash s, t;
char str[L];
void work(){
	int len=strlen(str);
	t.init();
	up(0,len-1)t.extend(str[o]);
	int d=0;
	for(int j=min(len,s.ls);j>=1;j--){
		if(equal(t.getHash(1,j),s.getHash(s.ls-j+1,s.ls))){
			d=j;
			break;
		}
	}
	for(int j=d;j<len;j++)s.extend(str[j]);
}
void solve(){
	//try it again.
	cin>>n;
	while(n--){
		cin>>str;
		work();
	}
	cout<<s.s+1<<endl;
}
signed main(){
	IOS;
	// int __;
	// cin>>__;
	// while(__--)
		solve();
    return 0;
}