How many different substrings are in a string?

Question

I need to design an algorithm in O (n) that given a string t of length n, calculate the number of different substrings of t.

Answer 1

1. Build a suffix automaton for the input string.

2. Find the sum of maxLength[v] - maxLength[suffixLink[v]] for all states v, where maxLength[v] is the longest path from the root to the v state and suffixLink[v] is a suffix link for this state.

Constructing a suffix automaton in a linear time is a well-known problem. The second part is just a simple traversal. Thus, the total time complexity is O(n).