(Initially we set $last = 0$, and we will change $last$ in the last step of the algorithm accordingly.)

- Create a new state $cur$, and assign it with $len(cur) = len(last) + 1$.

The value $link(cur)$ is not known at the time.

We start at the state $last$.

While there isn't a transition through the letter $c$, we will add a transition to the state $cur$, and follow the suffix link.

If at some point there already exists a transition through the letter $c$, then we will stop and denote this state with $p$.

- Suppose now that we have found a state $p$, from which there exists a transition through the letter $c$.

We will denote the state, to which the transition leads, with $q$.

- Now we have two cases. Either $len(p) + 1 = len(q)$, or not.

- In any of the three cases, after completing the procedure, we update the value $last$ with the state $cur$.

To do this, we take the state corresponding to the entire string (stored in the variable $last$), and follow its suffix links until we reach the initial state.

We will mark all visited states as terminal.

It is easy to understand that by doing so we will mark exactly the states corresponding to all the suffixes of the string $s$, which are exactly the terminal states.

- In the second case we came across an existing transition $(p, q)$.

This means that we tried to add a string $x + c$ (where $x$ is a suffix of $s$) to the machine that **already exists** in the machine (the string $x + c$ already appears as a substring of $s$).

However there is a difficulty.

To which state should the suffix link from the state $cur$ lead?

- The second place is the copying of transitions when the state $q$ is cloned into a new state $clone$.

- Third place is changing the transition leading to $q$, redirecting them to $clone$.

(The proof of the linearity of the number of states is the algorithm itself, and the proof of linearity of the number of states is given below, after the implementation of the algorithm).

Thus the total complexity of the **first and second places** is obvious, after all each operation adds only one amortized new transition to the automaton.

This is a suffix of the string $s$, and with each iteration its length decreases - and therefore the position $v$ as the suffix of the string $s$ increases monotonically with each iteration.

In this case, if before the first iteration of the loop, the corresponding string $v$ was at the depth $k$ ($k \ge 2$) from $last$ (by counting the depth as the number of suffix links), then after the last iteration the string $v + c$ will be a $2$-th suffix link on the path from $cur$ (which will become the new value $last$).

Therefore this cycle cannot be executed more than $n$ iterations, which was required to prove.

Again this task can be computed in $O(length(S))$ time.

}

Given a string $S$.

We have to answer multiple queries.

For each given number $K_i$ we have to find the $K_i$-th string in the lexicographically ordered list of all substrings.

The lexicographically $k$-th substring corresponds to the lexicographically $k$-th path in the suffix automaton.

Therefore after counting the number of paths from each state, we can easily search for the $k$-th path starting from the root of the automaton.

For a given text $T$.

We have to answer multiple queries.

We construct the suffix automaton for the text $T$.

Then we apply the following operation for each $v$: $cnt[link(v)] \text{ += } cnt[v]$.

The meaning behind this is, that if a string $v$ appears $cnt[v]$ times, then also all its suffixes appear at the exact same end positions, therefore also $cnt[v]$ times.

Because we add the positions of a state to only one other state, so it can not happen that one state directs its positions to another state twice in two different ways.

Thus we can compute the quantities $cnt$ for all states in the automaton in $O(length(T))$ time.