fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. string s;
  4.  
  5. vector<int> z_algo(){
  6.    int n = s.length();
  7.    vector<int>z(n,0);
  8.    int L = 0, R = 0;
  9.    for (int i = 1; i < n; i++) {
  10.       if (i > R) {
  11.          L = R = i;
  12.          while (R < n && s[R-L] == s[R]) R++;
  13.          z[i] = R-L; R--;
  14.       }
  15.       else {
  16.  
  17.          int k = i-L;
  18.          if (z[k] < R-i+1) z[i] = z[k];
  19.          else {
  20.             L = i;
  21.             while (R < n && s[R-L] == s[R]) R++;
  22.             z[i] = R-L; R--;
  23.          }
  24.       }
  25.    }
  26. return z;
  27. }
  28. int main(){
  29. 	cin>>s;int n=s.size();
  30. 	if(s.size() < 3){cout<<"Just a legend";return 0;}
  31. 	vector<int>z = z_algo();
  32. 	vector<int >::iterator it=z.begin();
  33. 	//for(int i=0;i<z.size();i++){
  34. 	//	z[i].push_back(i);
  35. 	//}
  36. 	int first=-1,second=-1;//store top two value indexes
  37. 	int maxi=-1,maxii=-1,i;
  38. 	for(i=0;it!=z.end();it++,i++){
  39. 		if((*it) > maxi){maxi=(*it);first=i;}
  40. 		//if((*it) > maxii)maxii=(*it),second=i;
  41. 	}
  42. 	it=z.begin();
  43. 	for(i=0;it!=z.end();it++,i++){
  44. 		//if((*it) > maxi){maxi=(*it);first=i;}
  45. 		if(i==first)continue;
  46. 		if((*it) > maxii)maxii=(*it),second=i;
  47. 	}
  48.  
  49. 	//sort(z.begin(),z.end());
  50. 	//f//or(i=0;i<z.size();i++){
  51. //		cout<<z[i];
  52. //	}
  53.  
  54. 	/*
  55. 	int counter=0;
  56. 	bool flag=false;
  57. 	cout<<first<<second<<maxi<<maxii;
  58. 	if(maxii==0 || maxi==0){cout<<"Just a legend";return 0;}
  59. 	if(first>second){cout<<"Just a legend";return 0;}
  60. 	else{flag=true;
  61. 	for(i=first;counter<maxii;counter++,i++){
  62. 		cout<<s[i];//cout<<"HIU";
  63. 	}
  64. 	return 0;
  65. 	}
  66. 	if(!flag){cout<<"Just a legend";}
  67. 	else{
  68.  
  69. 	}
  70.  
  71. 	*/
  72. 	int counter =0;
  73. 	string match = "";
  74. 	for(i=first;counter<maxii;counter++,i++){
  75. 		match+=s[i];
  76. 	}
  77. 	bool flag=true;
  78. 	for(i=0;i<maxii;i++){
  79. 		if(match[i]!=s[i]){flag=false;break;}
  80. 	}
  81. 	if(!flag){cout<<"Just a legend";return 0;}
  82. 	counter=0;
  83. 	for(i=n-maxii;counter<n-maxii,i<n;i++,counter++){
  84. 		if(match[counter]!=s[i]){flag=false;break;}
  85. 	}
  86. 	//cout<<first<<second<<maxi<<maxii;
  87. 	if(!flag){cout<<"Just a legend";return 0;}
  88. 	else{
  89. 		if(match=="")cout<<"Just a legend";
  90. 		else{
  91. 		cout<<match;
  92.  
  93. 		}
  94. 	}
  95. 	return 0;
  96. 	}
Success #stdin #stdout 0s 3236KB
comments ()
stdin
copy 
nadjnaddnajppn
stdout
copy 
4832Just a legend
https://ideone.com/Ddnf36
language:
C++ (gcc 8.3)
created:
9 years ago
visibility:
public

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!