fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. typedef long long ll;
  5. #define debug(x) cout<<#x<<" :: "<<x<<endl;
  6. #define debug2(x,y) cout<<#x<<" :: "<<x<<"\t"<<#y<<" :: "<<y<<endl;
  7.  
  8. #define n 100005
  9. int arr[n];
  10.  
  11. void lsp(string s,int l){
  12.   int i = 0,j = 1;
  13.   arr[0] = 0;
  14.   while(j<l){
  15.     if(s[i] == s[j]){
  16.       i++;
  17.       arr[j] = i;
  18.       j++;
  19.     }else{
  20.       if(i!=0) i = arr[i-1];
  21.       else{
  22.         j++;
  23.         arr[i] = 0;
  24.       }
  25.     }
  26.   }
  27. }
  28.  
  29. int main() {
  30.   int t;
  31.   cin>>t;
  32.   while(t--){
  33.     int len;
  34.     string s;
  35.     cin>>len>>s;
  36.     memset(arr,0,sizeof(arr));
  37.     lsp(s,len);
  38.     //cout<<"aman";
  39.     int a[len];
  40.     for(int i=0;i<=len;i++) a[i] = 0;
  41.  
  42.     for(int i=0;i<n;i++){
  43.       if(arr[i]!=0){
  44.         a[arr[i]]++;
  45.         //debug(arr[i]);
  46.       }
  47.     }
  48.  
  49.     int m = 0,ans;
  50.     for(int i=1;i<=len;i++){
  51.       if(a[i] >= m && a[i]!=0){
  52.         m = a[i];
  53.         ans = i;//cout<<i;
  54.       }
  55.     }
  56.     if(m) cout<<s.substr(0,ans);
  57.     else cout<<s;
  58.     cout<<endl;
  59.  
  60.   }
  61.   return 0;
  62. }
  63.  
Success #stdin #stdout 0s 15624KB
comments (?)
stdin
copy 
3
3
abc
5
thyth
5
abcbc
stdout
copy 
abc
th
abcbc
https://ideone.com/v5qMfM
language:
C++ 4.3.2 (gcc-4.3.2)
created:
5 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!