Exact Or Almost Certain

You must count the distinct substrings of a single string with $n = 5 \times 10^5$ characters, and the checker compares your number against an exact answer. Three plans are on the table:

Hash every substring length by length, put the hashes in a set, add up the set sizes. Simple, and you already have a hashing template.
Build a suffix array plus LCP array, answer with $n(n+1)/2 - \sum \text{lcp}[i]$ .
Build a suffix automaton, sum over states of len(v) - len(link(v)).

Which choice is right, and on what grounds?

Plan 3 only, because a suffix array needs $O(n \log^2 n)$ to build and $5 \times 10^5$ is past what that survives.

Either 2 or 3, because both are exact and linear or near-linear. Plan 1 is out on two counts: it is $O(n^2)$ in the number of substrings it enumerates, and even at a workable size a single hash collision changes the number the checker is reading.

Plan 1, because a double hash makes collisions negligible, and it is the least code to get right under time pressure.

Plan 2 only. A suffix automaton stores substrings by equivalence class, so it can count the classes but not the substrings themselves.