Cod sursă (job #377521)

#include <fstream>
#include <string>
using namespace std;
ifstream f("bart.in");
ofstream g("bart.out");
string s;
int repet[500002];
int main() {
    int n, curent=0, i, pos=1;
    f>>s;
    n=s.size();
    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;
}