CF 578 Div 2 E. Compress Words

https://codeforces.com/contest/1200/problem/E

The array used in KMP algorithm is useful to compute the length of common string. Someone may think this algorithm is squared time, but we don't have to treat whole string, so it works in linear time.

#include <bits/stdc++.h>
 
#define rep(i, n) for (int i = 0; i < (n); i++)
#define repr(i, n) for (int i = (n) - 1; i >= 0; i--)
 
using namespace std;
using ll = long long;
 
vector<int> kmp(string s) {
  int n = s.size();
  vector<int> p(n + 1);
  p[0] = -1;
  int j = -1;
  for (int i = 0; i < n; i++) {
    while (j != -1 && s[i] != s[j]) j = p[j];
    p[i + 1] = ++j;
  }
  return p;
}
 
int main() {
  cin.tie(nullptr); ios::sync_with_stdio(false);
  int n;
  cin >> n;
  string ans;
  rep(i, n) {
    string s;
    cin >> s;
    string tmp = ans.substr(max(0, (int)ans.size() - (int)s.size()));
    ans += s.substr(kmp(s + "$" + tmp).back());
  }
  cout << ans << endl;
}