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 (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
Anh Duc Le:
2015-04-26 11:27:10
Seems like the Cube cluster is really fast, even my simple O(NlogN) program using STL vector scored 100 ! |
|
Edward Grigoryan:
2015-03-27 09:59:13
My NlogN solution got 100.
|
|
Raihat Zaman Neloy:
2015-03-21 18:59:28
Yes Yes Yes!!! Got 100 Points! B-) Suffix Array O(n) Last edit: 2015-03-21 18:59:43 |
|
Rishit Sanmukhani:
2015-02-01 11:35:03
O(n(logn)^2) and O(nlogn) both gave 60 points. Used counting sort for nlogn |
|
Kamil:
2014-08-13 11:22:54
My n log^2 N also took 60 :) |
|
Kushal Saharan:
2014-06-28 07:10:17
@Felix Why won't solution ID:11844382 get more than 0 points? It seems to work correctly for all alphanumeric Characters on my computer? Last edit: 2014-06-28 07:10:46 |
|
maniAC:
2014-05-21 16:26:26
O(nlogn)-60 and O(nlog^2 n)-60 :v. Last edit: 2014-05-21 16:32:01 |
|
Bumbler:
2014-04-25 12:16:34
My O(nlogn) solution fetches 0 score with 0 K memory
|
|
leafmoon:
2014-01-26 12:29:49
Both sais() and divsufsort() got 100pts. Good... |
|
aqfaridi:
2014-03-04 17:20:43
naive approach..
|
Added by: | Felix Halim |
Date: | 2010-03-26 |
Time limit: | 0.200s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: PERL6 |