Suffix tree: Difference between revisions
Content added Content deleted
SqrtNegInf (talk | contribs) m (→{{header|Perl 6}}: updated output) |
|||
Line 614: | Line 614: | ||
├─$ |
├─$ |
||
└─na$</pre> |
└─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}}== |
=={{header|Racket}}== |