Cod sursă (job #378219)

#include <fstream>
#include <string.h>
using namespace std;
ifstream f("bart.in");
ofstream g("bart.out");
char s[500002];
int repet[500002];
int main() {
    int n, curent=0, i, pos=1;
    f>>s;
    n=strlen(s);
    for(i=1; i<=n; i++) {
        while (curent && (s[curent]!=s[pos])) {
            curent=repet[curent-1];
        }
        if (s[curent]==s[pos]){
            curent++;
        }
        repet[pos++]=curent;
    }
    s[n-repet[n-1]]='\0';
    g<<s;
    return 0;
}