fork(1) download
copy 
  1. #include<bits/stdc++.h>
  2. using namespace std;
  3. typedef int ll;
  4. const ll mx=200001;
  5. ll sa[mx],lcp[mx],pos[mx],tmp[mx];
  6. char a[mx];
  7. ll d=1,n;
  8. bool cmp(ll x,ll y){
  9.     if(pos[x]!=pos[y]) return pos[x]<pos[y];
  10.     x+=d;y+=d;
  11.     return pos[x%n]<pos[y%n];//x<n&&y<n?pos[x]<pos[y]:x>y for non-circular
  12. }
  13. void findSA(){
  14.     for(ll i=0;i<n;++i){
  15.         sa[i]=i;
  16.         pos[i]=a[i];
  17.     }
  18.     for(d=1;;d<<=1){
  19.     	sort(sa,sa+n,cmp);
  20.         tmp[0]=0;
  21.         for(ll i=1;i<n;++i) tmp[i]=tmp[i-1]+cmp(sa[i-1],sa[i]);
  22.         for(ll i=0;i<n;++i) pos[sa[i]]=tmp[i];
  23.         if(tmp[n-1]==n-1 || d>=n) break;
  24.     }
  25. }
  26. void findLCP(){
  27.     ll rank[mx];//non-circular may just use pos (suffixes are unique)
  28.     for(ll i=0;i<n;++i) rank[sa[i]]=i;
  29.     for(ll i=0, k=0;i<n;++i){
  30.         if(rank[i]<n-1) for(ll j=sa[rank[i]+1];k<n&&a[(i+k)%n]==a[(j+k)%n];++k);//non-circular: for(ll j=sa[rank[i]+1];i+k<n&&j+k<n&&a[i]==a[j];++k); 
  31.         else k = a[sa[0]]==a[i]?n:0;//remove this for non-circular
  32.         lcp[rank[i]]=k;
  33.         k=k-1>0?k-1:0;
  34.     }
  35. }
  36. int a1[mx];
  37. int ans[mx];
  38. int main(){
  39.     scanf("%d",&n);
  40.     for(ll i=0;i<n;++i) scanf("%d",a1+i);
  41.     for(ll i=0;i<n;++i) a[i]=(a1[i]<a1[(i+1)%n]?'a':'b');
  42.     findSA();
  43.     findLCP();
  44.     for (ll i=0;i<n;++i) {
  45.     	ll x = max(lcp[i],lcp[(i+n-1)%n])+1;
  46.     	ans[sa[i]] = x <= n ? x : -1;
  47.     }
  48.     for(ll i=0;i<n;++i) printf("%d\n",ans[i]);
  49.     return 0;
  50. }
Success #stdin #stdout 0.01s 7848KB
comments (?)
stdin
copy 
5
1
8
3
4
2
stdout
copy 
3
4
3
2
4
https://ideone.com/QaGEhB
Baekjoon 32846 finding keys nlog2n
language:
C++14 (gcc 8.3)
created:
9 days 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!