SARRAY - Suffix Array

no tags 

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 (0-based) 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(n2 log(n)) is expected to score about 20-30. (Naive sorting all suffixes)
O(n log2(n)) is expected to score about 40. (OK for most programming contest problems)
O(n log n) is expected to score about 60-70. (Use counting sort for small alphabet size)
O(n) without tweaks is expected to score about 80-90.
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
Hacking to the Gate: 2016-12-30 09:02:22

naive 30LOC, 40; n*log(n)^2, 90

Last edit: 2016-12-30 17:17:36
xehoth: 2016-12-27 12:35:20

SA-IS O(n) (with fread and fwrite)->100

hamjosh1: 2016-09-28 13:36:09

60 points with O(Nlog^2N) :(

Andres R. Arrieche S. [UCLA-ve]: 2015-10-31 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: 2015-10-18 22:33:56

O(nlog^2n) - 100 and am like... :D

alexbandeira: 2015-09-25 01:29:56

I do not think , 0 points :( Quest AC.

jarvis: 2015-09-18 13:02:24

0 points 0 memory :D green sign with o(n*logn*logn)

ihak: 2015-08-31 11:35:28

90 points with n * log n * logn .
Note : Operator overloading is quite faster I guess than normal function calls . That is the only thing I changed !
Infact I was using dynamic memory allocation too!
Not freeing the memory allocated dropped my time to 0.21 seconds.
Cannot permanently remove the dynamic memory allocation though :( Using classes

Last edit: 2015-08-31 11:36:44
rini22: 2015-08-29 07:18:03

O(n logn) + scanf,printf-----> 100

nishant bhardwaj: 2015-08-08 09:13:21

O(n * (log n)^2) gave me 90 :P


Added by:Felix Halim
Date:2010-03-26
Time limit:0.100s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: PERL 6