SARRAY  Suffix Array
Given a string of length at most 100,000 consist of alphabets and numbers. Output the suffix array of the string.
A suffix array is an array of integers giving the starting positions (0based) of suffixes of a string in lexicographical order. Consider a string "abracadabra0AbRa4Cad14abra". The size of the suffix array is equal to the length of the string. Below is the list of 26 suffixes of the string along with its starting position sorted in lexicographical order:
POS SUFFIX 11 0AbRa4Cad14abra 20 14abra 16 4Cad14abra 21 4abra 12 AbRa4Cad14abra 17 Cad14abra 14 Ra4Cad14abra 25 a 10 a0AbRa4Cad14abra 15 a4Cad14abra 22 abra 7 abra0AbRa4Cad14abra 0 abracadabra0AbRa4Cad14abra 3 acadabra0AbRa4Cad14abra 18 ad14abra 5 adabra0AbRa4Cad14abra 13 bRa4Cad14abra 23 bra 8 bra0AbRa4Cad14abra 1 bracadabra0AbRa4Cad14abra 4 cadabra0AbRa4Cad14abra 19 d14abra 6 dabra0AbRa4Cad14abra 24 ra 9 ra0AbRa4Cad14abra 2 racadabra0AbRa4Cad14abra
Note: this is a partial score problem.
O(n^{2} log(n)) is expected to score about 2030. (Naive sorting all suffixes)
O(n log^{2}(n)) is expected to score about 40. (OK for most programming contest problems)
O(n log n) is expected to score about 6070. (Use counting sort for small alphabet size)
O(n) without tweaks is expected to score about 8090.
O(n) with tweaks is expected to score 100. (This is meant for fun only :)
Input
A single line containing the string.
Output
The suffix array of the string.
Example
Input: abracadabra0AbRa4Cad14abra Output: 11 20 16 21 12 17 14 25 10 15 22 7 0 3 18 5 13 23 8 1 4 19 6 24 9 2
hide comments
beingbmc:
20190921 06:58:46
can someone provide an informative link about suffix array in O(n) ? 

darkdreamofmy1:
20181018 15:47:11
100 points in n long n


bessiethecow:
20181002 05:43:41
Got 100 using O(n log n) algorithm, with normal cin/cout for input and output. Didn't even have to turn off sync_with_stdio. Last edit: 20181003 06:04:08 

madhur4127:
20180515 06:09:16
i don't understand how 0.15s gets 60 and 0.25s gets 70!


tường:
20170301 13:11:14
My O(n (logn)^2) with printf, scanf still gets 100. 

Hacking to the Gate:
20161230 09:02:22
naive 30LOC, 40; n*log(n)^2, 90 Last edit: 20161230 17:17:36 

xehoth:
20161227 12:35:20
SAIS O(n) (with fread and fwrite)>100 

hamjosh1:
20160928 13:36:09
60 points with O(Nlog^2N) :( 

Andres R. Arrieche S. [UCLAve]:
20151031 22:19:04
My O(N*log^2 N) gives 80, 90, 100.... I don't know what's wrong but anyway I think 'cube cluster' gave us more points that deserved 

Marek Iwaniuk:
20151018 22:33:56
O(nlog^2n)  100 and am like... :D 
Added by:  Felix Halim 
Date:  20100326 
Time limit:  0.200s 
Source limit:  50000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  All except: PERL6 