Cod sursă (job #310812)

#include <cstdio>

#include <cstring>

#define MAX_N 500000

using namespace std;

FILE *f, *g;

int n;

int urm[MAX_N + 1];

char s[MAX_N + 2];

void readFile()
{
    f = fopen("bart.in", "r");

    fscanf(f, "%s", s + 1);

    n = strlen(s + 1);

    int i;
    int k = 0;
    for(i = 2; i <= n; i ++)
    {
        while(k > 0 && s[k + 1] != s[i])
            k = urm[k];

        if(s[k + 1] == s[i])
            k ++;

        urm[i] = k;
    }

    fclose(f);
}

void printFile()
{
    g = fopen("bart.out", "w");

    int i;
    for(i = 1; i <= n - urm[n]; i ++)
        fprintf(g, "%c", s[i]);

    fprintf(g, "\n");

    fclose(g);
}

int main()
{
    readFile();

    printFile();

    return 0;
}