Hi @adamant-pwn ,

I would like to contribute an efficient implementation of the suffix array construction algorithm in linear time (O(n)), using the SA-IS (Suffix Array Induced Sorting) algorithm or also called Skew Algorithm.

Key Steps:

1. Suffix Partitioning: The suffixes of a string are divided into three groups based on their positions:

   • (0 \mod 3)
   • (1 \mod 3)
   • (2 \mod 3)

2. Recursive Sorting: Suffixes from the (1 \mod 3) and (2 \mod 3) groups are sorted using radix sort, recursively processing until a small enough set is reached.

3. Merging: The sorted (1 \mod 3) and (2 \mod 3) suffixes are merged with the (0 \mod 3) suffixes to form the final sorted order.
   The Skew algorithm is notable for its combination of partitioning, recursion, and efficient merging to achieve linear-time suffix array construction.