The inefficient algorithm for suffix trie that we presented in our notes did not construct suffix links. We noted that suffix links are very important for algorithms such as finding the longest common substrings between two strings.

Let $$ be a string of length $$ and suppose we have found its suffix trie with root $.$ However, the trie has no suffix links.

Recall the notion of suffix links:

Every internal node $$ of the trie has a unique path from the root to $$ which is labeled with a non$-$empty substring of $.$

Suppose an internal node $\text{'}$s path from root corresponds to a substring of the form $$ where $$ is a character and $$ is an arbitrary length substring, then the suffix node $()$ is either the root or an internal node whose unique path from root is labeled by $.$

A suffix link is a link from each internal node $($and root$)$ to its suffix node $().$ For convenience, $()=.$

In this problem, we ask you to find an efficient algorithm for constructing suffix links in a suffix trie without them. The idea is to construct suffix links for internal nodes in a depthwise fashion.

The suffix link for the root is itself.

Suppose for a node $,$ the suffix link for its parent node $$ is known to be $(),$ we would like you to work out the suffix link for $$ knowing $()$ and the sub$-$string along the edge $->.$

In this manner, we can compute a depth first traversal of the tree and having computed the suffix link for the parent of a node, we can figure out the suffix link for the node itself.

First, we will ask you to work out the algorithm step by step and next, we will implement it$.$