How to solve this using Z algo , help needed. [Codeforces Beta Round #93 (Div. 1 Only)]

help
, ,
1

Question : “Problem - B - Codeforces”

How to solve this using Z algo I make Z array but after that I m stuck , i have no clue how to do in editorial they simply write this can be done by Z algo .

Please explain @galencolin @ay2306 (I saw your code too , can u explain please ) @ssjgz @everule1 @hetp111

2

@ay2306 's solution -

vector<int> z_val(string &a){
    int n = a.size();
    vector<int> z(n,0);
    int L = 0, R = 0;
    for(int i = 0; i < n ; ++i){
        if(i > R){
            L = R = i;
            while(R < n && a[R-L] == a[R])R++;
            z[i] = R-L; R--;
        }else{
            int k = i-L;
            if(z[k] < R-i+1)z[i]=z[k];
            else{
                L=i;
                while(R < n && a[R-L] == a[R])R++;
                z[i] = R-L; R--;
            }
        }
    }
    return z;
}

int main(){
    string a;
    cin >> a;
    auto z = z_val(a);
    int ans = 0;
    int n = a.size(),maxz=0;
    for(int i = 0; i < n; ++i){
        if(z[i] <= ans)continue;
        if(maxz >= n-i && z[i] == n-i){
             printf("index = %d, char = %c, z[i] = %d\n",i,a[i],z[i]);
            ans = n-i; break;
        }
        maxz = max(maxz,z[i]);
    }
    if(ans == 0)cout << "Just a legend";
    else for(int i = 0; i < ans; ++i)cout << a[i];
}

After Z algo what u did ? I don’t know -

Ex : “f i x p r e f i x s u f f i x”
Z - 0 0 0 0 0 03 0 0 0 0 1 3 0 0

Then ?