Suffix tree: Difference between revisions
→{{header|Phix}}
SqrtNegInf (talk | contribs) m (→{{header|Perl 6}}: updated output) |
|||
Line 614:
├─$
└─na$</pre>
=={{header|Phix}}==
{{trans|D}}
<lang Phix>-- tree nodes are simply {string substr, sequence children_idx}
enum SUB=1, CHILDREN=2
function addSuffix(sequence t, string suffix)
int n = 1, i = 1
while i<=length(suffix) do
integer ch = suffix[i], x2 = 1, n2
while (true) do
sequence children = t[n][CHILDREN]
if x2>length(children) then
-- no matching child, remainder of suffix becomes new node.
t = append(t,{suffix[i..$],{}})
t[n][CHILDREN] &= length(t)
return t
end if
n2 = children[x2]
if t[n2][SUB][1]==ch then exit end if
x2 += 1
end while
-- find prefix of remaining suffix in common with child
string prefix = t[n2][SUB]
int j = 0
while j<length(prefix) do
if suffix[i+j]!=prefix[j+1] then
-- split n2: new node for the part in common
t = append(t,{prefix[1..j],{n2}})
-- old node loses the part in common
t[n2][SUB] = prefix[j+1..$]
-- and child idx moves to newly created node
n2 = length(t)
t[n][CHILDREN][x2] = n2
exit -- continue down the tree
end if
j += 1
end while
i += j -- advance past part in common
n = n2 -- continue down the tree
end while
return t
end function
function SuffixTree(string s)
sequence t = {{"",{}}}
for i=1 to length(s) do
t = addSuffix(t,s[i..$])
end for
return t
end function
procedure visualize(sequence t, integer n=1, string pre="")
if length(t)=0 then
printf(1,"<empty>\n");
return;
end if
sequence children = t[n][CHILDREN]
if length(children)=0 then
printf(1,"- %s\n", {t[n][SUB]})
return
end if
printf(1,"+ %s\n", {t[n][SUB]})
integer l = length(children)
for i=1 to l do
puts(1,pre&"+-")
visualize(t,children[i],pre&iff(i=l?" ":"| "))
end for
end procedure
sequence t = SuffixTree("banana$")
visualize(t)</lang>
{{out}}
<pre>
+
+-- banana$
+-+ a
| +-+ na
| | +-- na$
| | +-- $
| +-- $
+-+ na
| +-- na$
| +-- $
+-- $
</pre>
=={{header|Racket}}==
| |||