Cod sursă (job #443938)

Utilizator	Prunescu Bogdan Bogdy_P	IP	ascuns
Problemă	Bart (clasele 9-10)	Compilator	cpp \| 0,46 kb
Rundă	Arhiva de probleme	Status	evaluat
Dată	7 mar. 2019 16:42:25	Scor	0

#include <bits/stdc++.h>

using namespace std;
ifstream in("bart.in");
ofstream out("bart.out");
char S[500001];
int l, p[500001], x;
int main()
{
    cin.getline((S + 1), 500001);
    l = strlen(S + 1);
    int q = 0;
    p[1] = 0;
    for(int i = 2;i <= l;i++)
    {
        while(S[i] != S[q + 1] && q > 0) q = p[q];
        if(S[i] == S[q + 1])q++;
        p[i] = q;
    }
    for(int i = 1;i <= l - p[l];i++)
        cout << S[i];
    return 0;
}