fork download
copy 
  1. /// Tested Code at: https://j...content-available-to-author-only...o.jp/submission/318835
  2.  
  3. #include<bits/stdc++.h>
  4. using namespace std;
  5.  
  6. const int N=1e6+5;
  7.  
  8. struct SuffixArray{
  9.     int lenS; string s;
  10.  
  11.     int rnk[N],sa[N],lcp[N];
  12.     int cntr,cnts,rnk2[N];
  13.     int head[N],lst[N],nxt[N];
  14.  
  15.     void push(int id, int val){
  16.         if(head[id]==-1){
  17.             head[id]=val;
  18.         } else{
  19.             nxt[lst[id]]=val;
  20.         }
  21.  
  22.         lst[id]=val;
  23.         nxt[val]=-1;
  24.     }
  25.  
  26.     void build_sa(){
  27.         /// sort with length 1 before lifting
  28.         for(int i=1; i<=lenS; ++i) push(s[i],i);
  29.         cnts=cntr=0;
  30.         for(int i=0; i<128; ++i){
  31.             if(head[i]==-1) continue;
  32.             ++cntr;
  33.  
  34.             int &j=head[i];
  35.             while(j!=-1){
  36.                 sa[++cnts]=j;
  37.                 rnk[j]=cntr;
  38.                 j=nxt[j];
  39.             }
  40.         }
  41.  
  42.         /// start lifting length
  43.         for(int len=1; len<lenS; len<<=1){
  44.             for(int i=lenS-len+1; i<=lenS; ++i){
  45.                 push(rnk[i],i);
  46.                 rnk2[i]=0;
  47.             }
  48.             for(int i=1; i<=lenS; ++i){
  49.                 if(sa[i]>len){
  50.                     push(rnk[sa[i]-len], sa[i]-len);
  51.                     rnk2[sa[i]-len]=rnk[sa[i]];
  52.                 }
  53.             }
  54.             cnts=cntr=0;
  55.             for(int i=1; i<=lenS; ++i){
  56.                 rnk2[sa[cnts]]=-1;
  57.  
  58.                 int &j=head[i];
  59.                 while(j!=-1){
  60.                     sa[++cnts]=j;
  61.                     if(rnk2[sa[cnts-1]]!=rnk2[j]) ++cntr;
  62.                     rnk[j]=cntr;
  63.                     j=nxt[j];
  64.                 }
  65.             }
  66.         }
  67.     }
  68.  
  69.     void build_lcp(){
  70.         int k=0;
  71.         for(int i=1; i<=lenS; ++i){
  72.             if(k) --k;
  73.             if(rnk[i]==lenS) continue;
  74.             int x=sa[rnk[i]+1];
  75.             while(max(i,x)+k<=lenS && s[i+k]==s[x+k]) ++k;
  76.             lcp[rnk[i]]=k;
  77.         }
  78.     }
  79.  
  80.     void init(const string &_s){
  81.         s=_s;
  82.         lenS=s.size(); s=" "+s; /// 1-indexed, can be switched
  83.  
  84.         memset(head,-1,sizeof(head));
  85.         build_sa();
  86.         build_lcp();
  87.  
  88.         for(int i=1; i<=lenS; ++i){
  89.             cout<<sa[i]-1<<" ";
  90.         }
  91.         cout<<'\n';
  92.     }
  93. } sigma;
  94.  
  95. int main(){
  96. //    freopen("test.inp","r",stdin);
  97.     string s; cin>>s;
  98.     sigma.init(s);
  99. }
Success #stdin #stdout 0.01s 11760KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 

	

		
	 
	
	
			

					
			
			
			
			
			
			
			
			

			
			
			
		

	
		
		

			

			                        







			
			

				

	
					
					 https://ideone.com/5zbZFP
					
					
					
					
					

												

												
						
						

					

					
					
					

						
language:

						
C++ (gcc 8.3)

					

					

						
created:
								
						
4 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!