Cod sursă (job #532097)

Utilizator	Jianu Ioana ioana.jianu	IP	ascuns
Problemă	Bart (clasele 9-10)	Compilator	cpp \| 0,65 kb
Rundă	Arhiva de probleme	Status	evaluat
Dată	28 feb. 2020 19:35:58	Scor	100

#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

const int NMAX = 500005;
char s[NMAX];
int Pi[NMAX];

int main() {

    freopen ("bart.in", "r", stdin);
    freopen ("bart.out", "w", stdout);

    int i, n, now;

    scanf ("%s", s);
    n = strlen(s);
    for (i = n; i >= 1; i--)
        s[i] = s[i - 1];

    for (i = 2; i <= n; i++) {
        now = Pi[i - 1];
        while (now > 0 && s[now + 1] != s[i])
            now = Pi[now];
        if (s[now + 1] == s[i])
            now++;
        Pi[i] = now;
    }

    for (i = 1; i <= n - Pi[n]; i++)
        printf ("%c", s[i]);

    return 0;
}