It is too stupid. There is another stupid way to construct suffix array for O(n * log(n) * log(n)). We need to sort suffixes using compare operation for O(log(n)). To compare substring for O(log(n)) we need to use polynomial hashes and binary search. With such a slow compare operation it is more efficient (20-30 percent faster) to use merge-sort or std::stable_sort. I have used this technique several times for building suffix array on strings with length 10^5-3*10^5 characters.

http://pastebin.com/WZb3WNQa
Took it here

Each of them is . There is an algorithm which works in .

For the first algorithm: In each step you calculate the order of suffixes of length "gap" so in the first iteration (iteration 0) you just sorts all the suffixes by the first letter, in the second by 2 letters, then by 4, 8, 16, 32 ... 2^k If you know the order of suffixes using only it's first 2^k letters then (using that information) you can calculate the order using first 2^(k + 1) letters; this is because each suffix of 2^(k + 1) can be seen as 2 contiguous suffixes of length 2^k of which you already have an "order" established.

For the second, you use binary search to find the first position where two suffixes are different, and then just compare those 2 chars. But this implementation using hashing can fail for some well known cases, that means that your solution could be easly hacked in a real CF round.

It is O(n lg n). It uses radix sort instead of quiksort, saving just a lg n factor.

what is the kasaiLCP () function ? what is its output ? in the other words, if we want to calculate the lcp(i,j) what should we do ?

LCP[i] = lcp(i,i-1) ?

one more thing !

i test this code , but it constructed false SA array for case "aaa" . for every string with all characters same and odd length , it produce wrong answer , can you help me what's going wrong ?

try this one and also Hidden Password

http://codeforces.net/gym/100133

DC3 is an overkill (depending on the task) and is practical for relative large inputs because its high constant factor.

For the n lg^2 n method described in my post, every line can be done in parallel:

1) sort(sa, sa + N, sufCmp);

2) REP(i, N — 1) tmp[i + 1] = tmp[i] + sufCmp(sa[i], sa[i + 1]);

3) REP(i, N) pos[sa[i]] = tmp[i];

1) Sorting is easy, eg use parallel_sort instead 2) Partial sums computation, this is also quite known, maybe you can use parallel_partial_sum instead. 3) Just parallelize the for (many libraries offer this feature, I'm almost sure that C++ (the newest standard with parallel extensions) support this also), each case is independent from the others.

At the end the algorithm scales nicely without any heavy modification.

PikaPika

Code in edit doesn't work, you can't modify pos[] to calculate tmp[], because the comparison uses pos[].

At each step suffixes are sorted based on the first 2^gap letters (from now this will be called the suffix length). To compare two suffixes (i and j) of length 2^(gap+1), you use the information of the previous suffix order (2^gap). The "weight" of the suffixes is stored in pos[]. Note that in the initial steps of the algorithm there can be two suffixes with the same "weight", that means that the first 2^gap letter of both suffixes are the same. Suffixes of length 2^(gap+1) can be seen as the concatenation of two suffixes of length 2^gap. Having calculated the "weight" of the suffixes of length 2^gap, we can safely compare suffixes i and j of length 2^(gap+1) using the pairs (pos[i], pos[i + gap]) and (pos[j], pos[j + gap]). The comparison first compares pos[i] and pos[j], if are equal, then uses pos[i+gap] and pos[j+gap]. Note that if i+gap or j+gap are not valid suffixes then the shorter comes first.

Indeed, but the original post is 2 years old, back then the hash flaw was not so popular.

Can you please explain how to break it?

It is Kasai's algorithm. I described it here.