Code : Compress Words

#include <bits/stdc++.h>
using namespace std;

vector<int> prefix_function(string &s) {
    int n = (int)s.length();
    vector<int> pi(n);
    for (int i = 1; i < n; i++) {
        int j = pi[i - 1];
        while (j > 0 && s[i] != s[j])
            j = pi[j - 1];
        if (s[i] == s[j])
            j++;
        pi[i] = j;
    }
    return pi;
}

void solve(vector<string> &vec) {
    int n = vec.size();

    string res = vec[0];
    for (int i = 1; i < n; i++) {
        string &now = vec[i];
        string temp = "";
        if (res.length() <= now.length()) {
            temp = now + '$' + res;
        } else {
            temp = now + '$' + res.substr(res.length() - now.length());
        }
        auto pi = prefix_function(temp);
        res += now.substr(pi.back());
    }
    cout << res << endl;
}

int main() {
    int n;
    cin >> n;
    vector<string> vec;
    for (int i = 0; i < n; i++) {
        string str;
        cin >> str;
        vec.push_back(str);
    }
    solve(vec);
    return 0;
}