class SuffixTrieNode:

def $\_\_$init$\_\_($self$,$ node$\_$id$,$ orig$\_$str$)$: self.orig$\_$str $=$ orig$\_$str # a reference to the entire string self.outgoing$\_$edges $=\{\}$ # dictionary from chars to edges self.suffix$\_$link $=$ None # suffix link : initially set to None self.id $=$ node$\_$id # Note: id $==0$ is taken to be root for now. self.depth $=0$ # automatically set the depth when node's parent is set self.parent $=$ None # parent pointer def is$\_$root$($self$)$: return self.id $==0$ def get$\_$edge$($self$,$ char$)$: if char in self.outgoing$\_$edges: return self.outgoing$\_$edges$[$char$]$ else: return None def is$\_$leaf$($self$)$: return False def add$\_$suffix$\_$link$($self$,$ node$)$: self.suffix$\_$link $=$ node def add$\_$outgoing$\_$edge$($self$,$ new$\_$edge$)$: edge$\_$init$\_$char $=$ new$\_$edge.get$\_$char$\_$at$(0)$ # ensure that an edge with the initial character does not exist assert edge$\_$init$\_$char not in self.outgoing$\_$edges, f$"$Char $\{$edge$\_$init$\_$char$\}$ already has an outgoing edge for node id:$\{$self$.$id$\}"$ #ensure that the new$\_$edge src matches self assert new$\_$edge.src$.$id $==$ self.id$,$ f$"$Src node in outgoing edge id:$\{$new$\_$edge.src$.$id$\}$ does not match node id $\{$self$.$id$\}"$ # add the new edge to the dictionary with the initial char as key self.outgoing$\_$edges$[$edge$\_$init$\_$char$]=$ new$\_$edge # add a parent pointer from destination to the src of the new edge new$\_$edge.dest.parent $=$ new$\_$edge.src # set the parent pointer of the new edges dest if not new$\_$edge.is$\_$leaf$\_$edge$()$: # set the depth of the destination node for the edge new$\_$edge.dest.depth $=$ self.depth $+$ new$\_$edge.length$()$ def find$\_$edge$\_$corresponding$\_$to$\_$child$($self$,$ child$\_$node$)$: # search among outgoing edges to see if there is one whose destination is the child node for $(\_,$ edge$)$ in self.outgoing$\_$edges.items$()$: if edge.dest.id $==$ child$\_$node.id: return edge return None # no such edge found class SuffixTrieLeaf: def $\_\_$init$\_\_($self$,$ node$\_$id$,$ orig$\_$str$,$ suffix$\_$start$\_$pos$)$: self.orig$\_$str $=$ orig$\_$str # the original string self.id $=$ node$\_$id # the id of this node assert $0<=$ suffix$\_$start$\_$pos $<$ len$($orig$\_$str$)$ self.suffix$\_$start$\_$pos $=$ suffix$\_$start$\_$pos # the starting pos for the suffix self.parent $=$ None # parent pointer initially set to None def is$\_$leaf$($self$)$: return True class SuffixTrieEdge: def $\_\_$init$\_\_($self$,$ orig$\_$str$,$ src$\_$node, dest$\_$node, lo$,$ hi$)$: assert $0<=$ lo $<$ len$($orig$\_$str$)$ # lo must be a valid position in the original string # if destination node is a leaf then hi $==-1$ else hi $!=-1$ if dest$\_$node.is$\_$leaf$()$: assert hi $==-1$ else: assert lo $<=$ hi $<=$ len$($orig$\_$str$)$ assert not src$\_$node.is$\_$leaf$()$ # src node cannot be a leaf. # edge represents str$[$lo$]...$str$[$hi$]$ inclusive if hi $!=-1$ # or set$[$lo$]...$ str$[$end$]$ self.orig$\_$str $=$ orig$\_$str # set the orig$\_$str field self.lo $=$ lo # set lo$/$hi self.hi $=$ hi self.src $=$ src$\_$node # set src$/$dest self.dest $=$ dest$\_$node def is$\_$leaf$\_$edge$($self$)$: return self.hi $==-1$ def length$($self$)$: if self.hi $==-1$: return $-1$ else: return self.hi $-$ self.lo $+1$ def get$\_$char$\_$at$($self$,$ offs$)$: assert self.hi $==-1$ or offs $+$ self.lo $<=$ self.hi return self.orig$\_$str$[$self$.$lo $+$ offs$]$ def get$\_$sub$\_$str$($self$,$ end$=-1)$: if self.hi $==-1$: return self.orig$\_$str$[$self$.$lo:end$]$ if $($end $!=-1)$ else self.orig$\_$str$[$self$.$lo:$]$ else: return self.orig$\_$str$[$self$.$lo:self.hi$+1]$ def reset$\_$hi$\_$and$\_$dest$($self$,$ new$\_$dest, new$\_$hi$)$: assert new$\_$hi $>=$ self.lo$,$ f$"$Cannot replace hi value by $\{$new$\_$hi$\}"$ assert not new$\_$dest.is$\_$leaf$(),$ "Cannot replace destination by a leaf node" self.hi $=$ new$\_$hi new$\_$dest.parent $=$ self.src new$\_$dest.depth $=$ self.src$.$depth $+$ self.length$()$ self.dest $=$ new$\_$dest class TrieAddress: def $\_\_$init$\_\_($self$,$ node, edge$=$None, offs$=0)$: assert $0<=$ offs self.node $=$ node # set the node self.edge $=$ edge # set the edge self.offs $=$ offs # set the offset if self.edge $!=$ None: assert self.offs $>0$ else: assert self.offs $==0$ def traverse$\_$next$($self$,$ c$)$: $"""$Function traverse$\_$next: find the next address $($if one exists$)$ that is obtained when we encounter character c$.$ Return the new address if one exists or else return None.""" if self.edge $==$ None: # Is the address pointing to an internal node? # Yes: address is just a pointer to an internal node$/$root$.$ # check if the node has an outgo