Complete the implementation of the function add$\_$all$\_$suffix$\_$links that given a suffix trie without suffix links, walks the trie from root down to leaves and computes suffix nodes for a child node given that of a parent node. In particular, we would like you to complete the get$\_$suffix$\_$link$\_$for$\_$dest$\_$node function below as speficied.

def add$\_$all$\_$suffix$\_$links$($root$,$ debug$=$True$)$:

root.add$\_$suffix$\_$link$($root$)$ # root must be suffix linked to itself.

worklist $=[]$ # a list of edges wherein parent has a suffix link but child does not

for $(\_,$ edge$)$ in root.outgoing$\_$edges.items$()$:

# iterate through all outgoing edges of the root

if not edge.is$\_$leaf$\_$edge$()$:

worklist.append$($edge$)$ # add the edge from root to an internal non$-$leaf node to the worklist.

## now iterate through the worklist

while len$($worklist$)>=1$:

edge $=$ worklist.pop$()$

assert not edge.is$\_$leaf$\_$edge$()$

p $=$ edge.src

n $=$ edge.dest

# this is an edge from parent p to node n

s$\_$n $=$ get$\_$suffix$\_$link$\_$for$\_$dest$\_$node$($edge$)$ # use the edge data to get the suffix node

n$.$add$\_$suffix$\_$link$($s$\_$n$)$

if debug:

print$($f$\text{'}$Adding suffix link n$\{$n$.$id$\}-->$ n$\{$s$\_$n$.$id$\}\text{'})$

for $(\_,$ next$\_$edge$)$ in n$.$outgoing$\_$edges.items$()$:

if not next$\_$edge.is$\_$leaf$\_$edge$()$:

worklist.append$($next$\_$edge$)$

return

def get$\_$suffix$\_$link$\_$for$\_$dest$\_$node$($edge$)$:

p $=$ edge.src

n $=$ edge.dest

assert p$.$suffix$\_$link $!=$ None, f$"$parent $\{$p$.$id$\}$ has no suffix link but asking for the suffix link of a child"

assert not edge.is$\_$leaf$\_$edge$()$

orig$\_$str $=$ edge.orig$\_$str

lo $=$ edge.lo

hi $=$ edge.hi

assert $0<=$ lo $<=$ hi and hi $<$ len$($orig$\_$str$)$

## TODO: implement the algorithm to find the suffix link of n

## given that of p and the data for the edge from p $->$ n