# 「SPOJ-SARRAY」-后缀数组-SA-IS

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:

SPOJ-SARRAY

### 输入

A single line containing the string.

### 输出

The suffix array of the string.

### 题解

Note: this is a partial score problem.
$O(n^2 \log(n))$ is expected to score about $20-30$. (Naive sorting all suffixes)
$O(n \log 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 :)

$0s$ $AC$，23333333…..