l5aL6R - Online C++ Compiler & Debugging Tool

#include <bits/stdc++.h>
#define ll long long
#define all(a) (a).begin(), (a).end()
#define dbg_line(x) cout << (x) << '\n'
#define dbg(x) cout << x << " "

using namespace std;

// <--> Report constants <-->

typedef pair<int, int> pii;
const int max_n = 1e6 + 5;
const ll inf = 1e9;
const ll m_inf = -1e9;
const ll mod = 1e9 + 7;
const int base = 32;

// <--> Report variables <-->

ll pref[max_n];
ll mult[max_n];

// <--> Main Code is Here <-->

void setIO(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
}

void call_file(){
    freopen("input.txt","r",stdin);
    freopen("output.txt","w",stdout);
}

void buildHash(string s){
    pref[0] = 0;
    mult[0] = 1;

    int n = s.length();
    for (int i = 1; i <= n; i++){
        pref[i] = (pref[i - 1] * base + s[i - 1] - 'a' + 1) % mod;
        mult[i] = (mult[i - 1] * base) % mod;
    }
}

ll getHashString(string s){
    ll result = 0;
    for (char c: s){
        result = (result * base + c - 'a' + 1) % mod;
    }
    return result;
}

ll getHash(int l, int r){
    return (pref[r] - (pref[l - 1] * mult[r - l + 1]) % mod + mod) % mod;
}

int main(){
    setIO();
    call_file();
    int n;
    cin >> n;
    string res = "";
    string t;
    cin >> t;
    res += t;
    string prev = t;
    for (int i = 1; i < n; i++){
        string s;
        cin >> s;
        buildHash(s);
        string tmp = "";
        int right = 0;
        for (int j = prev.size() - 1; j >= 0; j--){
            tmp = prev[j] + tmp;
            int hashTmp = getHashString(tmp);
            if (tmp.size() > s.size()){
                break;
            }
            if (getHash(1, tmp.size()) == hashTmp){
                right = tmp.size();
            }
        }
        for (int j = right; j < s.size(); j++){
            res += s[j];
        }
        prev = s;
    }
    cout << res;
}