https://rosettacode.org/wiki/Suffix_tree#M2000_Interpreter
https://en.wikipedia.org/wiki/Suffix_tree
'https://rosettacode.org/wiki/Suffix_tree
Module Suffix_tree {
Class SuffixTree {
Private:
Nodes=List
' Class definition which return a pointer to object
Class Node {
String sub
ch=list
{
Read Node.sub, Node.ch
->(Node)
break
}
}
module addSuffix (suf as String) {
long n = 0, i = 0, x2, n2
String b
tmp=list
While i < Len(suf)
b=mid(suf,i+1,1)
x2=0
n2=0
do
children=.Nodes(n).ch
if x2=len(children) Then
n2=len(.Nodes)
.Nodes(n2)=.Node(Mid$(suf, i+1))
children(X2)=n2
break ' Exit module
End if
n2=children(x2)
if left(.Nodes(n2).sub,1)=b Then Exit ' Exit do
x2++
Always
sub2=.Nodes(n2).sub
long j=0
While j<len(sub2)
if mid(suf,i+1+j,1)<>mid(sub2, j+1,1) Then
n3=n2
n2=len(.Nodes)
.Nodes(n2)=.Node(Left(sub2,j), List:=0:=n3)
.Nodes(n3).sub=Mid(sub2, j+1)
.Nodes(n).ch(X2)=n2
Exit
End if
j++
End While
i+=j
n=n2
End While
}
Public:
module visualize {
if len(.Nodes)=0 Then ? "<empty>":Exit
visualize_f(0, "")
sub visualize_f(n as long, pre as string)
Local children=.Nodes(n).ch
if len(children)=0 Then
? "- "+.Nodes(n).sub
Else
? "┐ "+.Nodes(n).sub
Pr each(children, 1 , -2), "├─"
Pr each(children, -1), "└─"
End if
End sub
Sub Pr(ch, pre2 as string)
While ch
? pre + pre2;
visualize_f(Eval(ch), pre + "│ ")
End While
End Sub
}
Class:
module SuffixTree (Str as String) {
if len(Str)=0 Then Error "need one character...at least"
.Nodes(0)=.Node()
for i=1 to len(Str)
.addSuffix Mid(Str, i)
next
}
}
M=SuffixTree("banana$")
M.visualize
}
Suffix_tree
