//
// Suffix Array (Manbar and Myers' O(n (log n)^2))
//
// Description:
// For a string s, tts suffix array is a lexicographically sorted
// list of suffixes of s. For example, for s = "abbab", its SA is
// 0 ab
// 1 abbab
// 2 b
// 3 bab
// 4 bbab
//
// Algorithm:
// Manbar and Myers' doubling algorithm.
// Suppose that suffixes are sorted by its first h characters.
// Then, the comparison of first 2h characters is computed by
// suf(i) <_2h suf(j) == if (suf(i) !=_h suf(j)) suf(i) <_h suf(j)
// else suf(i+h) <_h suf(j+h)
//
// Complexity:
// O(n (log n)^2).
// If we use radix sort instead of standard sort,
// we obtain O(n log n) algorithm. However, it does not improve
// practical performance so much.
//
// Verify:
// SPOJ 6409: SARRAY (80 pt)
//
#include