There were rumors that it is hard to get AC with hashes.
Got AC in 0.031 using standard N log^2 N suffix array. Hashes modulo 2^64 (so there is no explicit divisions in code).
There are couple of tricks, but they all are very easy to code.

1) gethash(i + l, i + mid) == gethash(j + l, j + mid)
&& memcmp(s + i + l, s + j + l, mid - l) == 0
instead of just
gethash(i, i + mid) == gethash(j, j + mid)
in binary search (lcp computing)

2) std::::stable_sort is preferable over std::sort when comparisons are heavy. std::stable_sort makes more assignments in average, but much less comparisons.

0.031 sec, 62 lines of code (including 10 empty, "return 0", 4 includes and so on).

The rumors said that it was hard to get AC with hashes in O(n^2): to calculate hashes of all substrings and output the number of different ones :)

I got AC by output number of different hashes in O(n^2).
Took some tries though. Ended up using double hash, one which uses long long overflow and one modulo some big prime. I think test 27 is anti-hash test.

Edited by author 27.01.2018 02:09