fork download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3.  
  4. int * Z_algo(string s,int n){
  5.     int *z=new int[n];
  6.     int l=0,r=0;
  7.  
  8.     for(int i=1;i<n;i++){
  9.         //condition 1
  10.         if(i>r){
  11.             l=i;
  12.             r=i;
  13.             while(r<n and s[r-l]==s[r]){
  14.                 r++;
  15.             }
  16.             r--;
  17.             z[i]=r-l+1;
  18.  
  19.         }
  20.         //condition 2
  21.         else{
  22.             int j=i-l;
  23.  
  24.             //condition 2a
  25.             if(z[j]<r-i+1){
  26.                 z[i]=z[j];
  27.             }
  28.             //condition 2b
  29.             else{
  30.                 l=i;
  31.                 while(r<n and s[r-l]==s[r]){
  32.                     r++;
  33.                 }
  34.                 r--;
  35.                 z[i]=r-l+1;
  36.             }
  37.         }
  38.     }
  39.     return z;
  40. }
  41.  
  42. int main(){
  43.     string s;
  44.     cin>>s;
  45.     int n=s.size();
  46.     int *z=Z_algo(s,n);
  47.     int maxi=0,ans=-1;
  48.     for(int i=1;i<n;i++){
  49.         if(z[i]==n-i && maxi>=n-i){
  50.             ans=n-i;
  51.             break;
  52.         }
  53.         maxi=max(maxi,z[i]);
  54.     }
  55.     if(ans==-1){
  56.         cout<<"Just a legend";
  57.     }
  58.     else{
  59.         cout<<s.substr(n-ans,ans);
  60.     }
  61.     return 0;
  62. }
Success #stdin #stdout 0s 4484KB
comments (?)
stdin
copy 
fixprefixsuffix
stdout
copy 
fix
https://ideone.com/qKivcB
language:
C++14 (gcc 8.3)
created:
5 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!