Suffix Automaton

Source :

Link1 Link2 Link3

Code :

Application :

1. Find pattern P in text T in O(|T| + |P|).

:: Build the automaton then loop through P and find if there exists transitions.

2. Find number of distinct sub-strings in S.

:: These can be calculated recursively by calculating for each node the number of different paths starting from that node. The number of different paths starting from a node is the sum of the corresponding numbers of its direct successors, plus 1 corresponding to the path that does not leave the node.

3. Total length of all distinct sub-strings in S.

:: From previous code we know value of dp[i]. Now, we will do same thing here ans[u] += ans[v] + dp[v].

4. The lexicography Kth sub-string  in S. (only distinct sub-strings / all possible sub-strings)

:: (distinct) Pick the transition with smallest character then if the path length becomes K, we will return the character and take all visited characters from that path. 

:: (Not distinct) First we will find all occurrence of each sub-strings. Then we will Find Kth smallest sub-string. See this.

[Let cnt[v] is the For all the states v number of occurrence of the sub-strings associated with v.
Initially if state v was not cloned then cnt[v] = 1 , otherwise it’s 0. We go through each state in descending order of length. and for each state we do cnt[link[v]]+=cnt[v]; After that , if u is the state corresponding to pattern P , then cnt[u] is the ans.]

5. (...)