Cod sursă (job #585152)

#include <iostream>
#include <fstream>
#include <cstring>
#define MAXN 500001

using namespace std;
ifstream fin("bart.in");
ofstream fout("bart.out");
char cuv[MAXN];
int rez,lps[MAXN];
void getLPSarray(){
    int j=0,i=1;
    lps[0]=0;
    while(i<strlen(cuv)){
        if(cuv[i] == cuv[j]){
            lps[i] = j+1;
            if(lps[i] == 1){
                rez = i;
            }
            j++;
            i++;
        }
        else{
            if(j != 0)
                j = lps[j-1];
            else{
                lps[i] = 0;
                i++;
            }
        }
    }
}
int main(){
    fin>>cuv;
    getLPSarray();
    //for(int i=0;i<strlen(cuv);i++)
      //  cout<<lps[i]<<' ';
    //cout<<rez;
    for(int i = 0; i < rez; i++){
        fout<<cuv[i];
    }
    return 0;
}