Suffix tree: Difference between revisions
J
(Go solution) |
(J) |
||
Line 121:
└─╴ $
</pre>
=={{header|J}}==
Implementation:
<lang J>classify=: {.@> </. ]
root=: ,:__;_;''
build_tree=:3 :0
if. 0=#y do. i.0 3 return.end.
if. 1=#y do. root,(#;y);0;y return.end.
tree=. root
for_box.classify y do.
char=. {.>{.>box
subtree=. }.build_tree }.each>box
ndx=.I.0=1&{::"1 subtree
if. 1=#ndx do.
tree=. tree, (]1+&.>{.)`0:`]}~"1 subtree ndx}~ char ((,L:0 {:)`2:`])} {.ndx{subtree
else.
n=.#tree
tree=. tree,(__;0;,char),(1;n;0) + ::]&.>"1 subtree
end.
end.
)
suffix_tree=:3 :0
assert. -.({:e.}:)y
tree=. B=:|:build_tree <\. y
((1+#y)-each {.tree),}.tree
)</lang>
Task example:
<lang J> suffix_tree 'banana$'
┌─┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│_│1 │_│_ │2 │4│6│_ │3 │5│7│
├─┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│_│0 │0│2 │3 │3│2│0 │1 │1│0│
├─┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
└─┴───────┴─┴──┴───┴─┴─┴──┴───┴─┴─┘</lang>
The first row is the leaf number (_ for internal nodes).
The second row is parent index (_ for root node).
The third row is the edge's substring (empty for root node).
=={{header|Perl}}==
| |||