Скачать или смотреть Advanced Data Structures | Suffix Array [02] Suffix Array Construction | شرح بالعربي

Suffix Array
Suffix Array Construction
suffix array construction algorithm
prefix doubling algorithm
prefix doubling
==============================
Download Materials :
https://github.com/Abdalla2030/Educat...
==============================
O(n Log n) algorithm for suffix array construction is discussed. Let us first discuss a O(n * Logn * Logn) algorithm for simplicity.

The idea is to use the fact that strings that are to be sorted are suffixes of a single string.

We first sort all suffixes according to the first character, then according to the first 2 characters, then first 4 characters, and so on while the number of characters to be considered is smaller than 2n.
The important point is, if we have sorted suffixes according to first 2i characters, then we can sort suffixes according to first 2i+1 characters in O(n Log n) time using a (n Log n) sorting algorithm like Merge Sort.
This is possible as two suffixes can be compared in O(1) time (we need to compare only two values, see the below example and code).

The sort function is called O(Logn) times (Note that we increase the number of characters to be considered in powers of 2). Therefore overall time complexity becomes O(nLognLogn).