fork download
copy 
  1. # include <iostream>
  2. # include <algorithm>
  3. # include <cstring>
  4.  
  5. using namespace std;
  6.  
  7. struct tpl{
  8. int fhf,nhf,indx;
  9. }*tlst;
  10.  
  11.  
  12. void out(int *&x,int st,int en){
  13. st-=1;
  14. while(++st<en)cout<<x[st]<<" ";
  15. cout<<endl;
  16. }
  17.  
  18. void disp(tpl *&x,int st,int en){
  19. st-=1;
  20. while(++st<en)cout<<"First Half : "<<x[st].fhf<<" Next Half : "<<x[st].nhf<<" index "<<x[st].indx<<endl;
  21. }
  22.  
  23. void inverse(int *x,int *y,int len){
  24. for(int i=0;i<len;y[x[i]]=i,++i);
  25. }
  26.  
  27. // if l<r : -1, l==r : 0 , l>r 1
  28. int cmpre(const void *l, const void *r){
  29. 	if((*(tpl *)l).fhf < (*(tpl *)r).fhf)return -1;
  30. 	else if((*(tpl *)l).fhf == (*(tpl *)r).fhf){
  31. 		if((*(tpl *)l).nhf == (*(tpl *)r).nhf)  return 0;
  32. 		else if((*(tpl *)l).nhf > (*(tpl *)r).nhf)  return 1;
  33. 		else return -1;
  34. 	}
  35. 	else return 1;
  36. }
  37.  
  38. int cmpr(const tpl &l, const tpl &r){
  39. 	if(l.fhf < r.fhf)return -1;
  40. 	else if(l.fhf == r.fhf){
  41. 		if(l.nhf == r.nhf)  return 0;
  42. 		else if(l.nhf > r.nhf)  return 1;
  43. 		else return -1;
  44. 	}
  45. 	else return 1;
  46. }
  47.  
  48. int sa(char *&x,int *&sarr){
  49.  
  50. 	int len = strlen(x);
  51. 	int rank[len];
  52.  
  53. 	tlst = new tpl[len];
  54.  
  55. 	for(int i=0;x[i];tlst[i].fhf = x[i]-97,tlst[i].indx=i,++i);
  56.  
  57. 	int cnt = 1;
  58.  
  59. 	while(cnt<len){
  60.  
  61. 		for(int i=0;i<len;++i)
  62. 			tlst[i].nhf = i+cnt < len ? tlst[i+cnt].fhf : -1;
  63.  
  64.  
  65. 		//	For Tracing
  66.         cout<<"\tBefore Sort -> "<<endl;
  67.         disp(tlst,0,len);
  68.  
  69. 		 qsort(tlst,len,sizeof(tpl),cmpre);
  70. 		// sort(tlst,tlst+len,cmpr);
  71.  
  72.  
  73. 		//	For Tracing
  74. 		cout<<"\tAfter Sort -> "<<endl;
  75.         disp(tlst,0,len);
  76.  
  77.  
  78. 		rank[tlst[0].indx] = 0;
  79. 		for(int i=1;i<len;++i)
  80. 			rank[tlst[i].indx] = tlst[i].fhf == tlst[i-1].fhf && tlst[i].nhf == tlst[i-1].nhf ? rank[tlst[i-1].indx] : i;
  81. 		for(int i=0;i<len;tlst[i].fhf = rank[i],tlst[i].indx = i,++i);
  82.  
  83. 			cnt<<=1;
  84.  
  85. 	}
  86.  
  87. 	inverse(rank,sarr,len);
  88.  
  89. 	return len;
  90.  
  91. }
  92. int main(){
  93.  
  94. 	char *str = new char[100]();
  95. 	strcpy(str,"gatagaca");
  96.  
  97. 	int *sarr = new int[100]();
  98.  
  99. 	sa(str,sarr);
  100.  
  101.  
  102. 	return 0;
  103. }
  104.  
Success #stdin #stdout 0s 3464KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
	Before Sort -> 
First Half : 6 Next Half : 0 index 0
First Half : 0 Next Half : 19 index 1
First Half : 19 Next Half : 0 index 2
First Half : 0 Next Half : 6 index 3
First Half : 6 Next Half : 0 index 4
First Half : 0 Next Half : 2 index 5
First Half : 2 Next Half : 0 index 6
First Half : 0 Next Half : -1 index 7
	After Sort -> 
First Half : 0 Next Half : -1 index 7
First Half : 0 Next Half : 2 index 5
First Half : 0 Next Half : 6 index 3
First Half : 0 Next Half : 19 index 1
First Half : 2 Next Half : 0 index 6
First Half : 6 Next Half : 0 index 0
First Half : 6 Next Half : 0 index 4
First Half : 19 Next Half : 0 index 2
	Before Sort -> 
First Half : 5 Next Half : 7 index 0
First Half : 3 Next Half : 2 index 1
First Half : 7 Next Half : 5 index 2
First Half : 2 Next Half : 1 index 3
First Half : 5 Next Half : 4 index 4
First Half : 1 Next Half : 0 index 5
First Half : 4 Next Half : -1 index 6
First Half : 0 Next Half : -1 index 7
	After Sort -> 
First Half : 0 Next Half : -1 index 7
First Half : 1 Next Half : 0 index 5
First Half : 2 Next Half : 1 index 3
First Half : 3 Next Half : 2 index 1
First Half : 4 Next Half : -1 index 6
First Half : 5 Next Half : 4 index 4
First Half : 5 Next Half : 7 index 0
First Half : 7 Next Half : 5 index 2
	Before Sort -> 
First Half : 6 Next Half : 5 index 0
First Half : 3 Next Half : 1 index 1
First Half : 7 Next Half : 4 index 2
First Half : 2 Next Half : 0 index 3
First Half : 5 Next Half : -1 index 4
First Half : 1 Next Half : -1 index 5
First Half : 4 Next Half : -1 index 6
First Half : 0 Next Half : -1 index 7
	After Sort -> 
First Half : 0 Next Half : -1 index 7
First Half : 1 Next Half : -1 index 5
First Half : 2 Next Half : 0 index 3
First Half : 3 Next Half : 1 index 1
First Half : 4 Next Half : -1 index 6
First Half : 5 Next Half : -1 index 4
First Half : 6 Next Half : 5 index 0
First Half : 7 Next Half : 4 index 2
https://ideone.com/zN87tX
language:
C++14 (gcc 8.3)
created:
7 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!