Cod sursă (job #532233)

Utilizator avatar anastasiastef Anastasia Stefanescu anastasiastef IP ascuns
Problemă Bart (clasele 9-10) Compilator cpp | 0,72 kb
Rundă Arhiva de probleme Status evaluat
Dată 29 feb. 2020 10:21:30 Scor 0
//
//  main.cpp
//  probleme2018-2019 (este 2020 noobule)

#include <fstream>
#include <iostream>
using namespace std;
ifstream fin ("bart.in");
ofstream fout ("bart.out");

char s[500001], x, pi[500001], now;
int n;

void calc_pi(char v[500001])
{
    int i;
    pi[1] = 0;
    
    for (i = 2; i<= n; i++)
    {
        now = pi[i-1];
        while (s[now+1] != s[i] && now > 0)
            now = pi[now];
        if(s[now+1] == s[i])
            now++;
        pi[i] = now;
    }
}

int main()
{
    int i;
    x = fin.get();
    while (x != '\n' && x != EOF)
    {
        n++;
        s[n] = x;
        x = fin.get();
    }
    
    calc_pi(s);
    for (i=1;i<=n-pi[n];i++)
        fout<<s[i];
    return 0;
}

//program functional