Cod sursă (job #617565)

#include <bits/stdc++.h>

using namespace std;

const int NMAX = 5e5;
int z[NMAX + 5];
int n;

int main()
{
    ifstream fin("bart.in");
    ofstream fout("bart.out");
    int l = 0,r = 0;
    string s;
    fin >> s;
    n = s.size();
    for (int i = 1;i < n;i++) {
      if (i <= r)
        z[i] = min(r - i + 1, z[i - l]);
      while (i + z[i] < n && s[i + z[i]] == s[z[i]])
        z[i]++;
      if (i + z[i] - 1 > r) {
        r = i + z[i] - 1;
        l = i;
      }
    }
    for (int i = 1;i <= n;i++) {
      if (z[i] == n - i) {
        for (int j = 0;j < i;j++)
          fout << s[j];
        break;
      }
    }
    return 0;
}