This problem is based on Z- algorithm

To learn this algorithm – Click here!

## View Code

#include<bits/stdc++.h>

using namespace std;

void solve(string s)

{

int l=s.size();

int z[l];

int left,right;

left=right=0;

for(int k=1;k<l;k++) { if(k>right)

{

left=right=k;

while(right {

right++;

}

z[k]=right-left;

right–;

}

else{

int k1=k-left;

if(z[k1]<right-k+1)

{

z[k]=z[k1];

}

else{

left=k;

while(right {

right++;

}

z[k]=right-left;

right–; }

}

}

int mxz = 0, res = 0,n=l;

for(int a=1;a<l;a++){

//printf(“%d %d\n”, a, Z[a]);

if(a + z[a] == l){

if(z[a] <= mxz){

for(int j=0;j<z[a];j++) printf(“%c”, s[j]); return ; } } mxz = max(mxz, z[a]); } puts(“Just a legend”); } int main() { string s; cin>>s;

solve(s);

}

Advertisements