Jump to content

Suffix tree: Difference between revisions

Suffix tree (view source)

Revision as of 17:37, 28 August 2022

584 bytes added ,  1 year ago
m
syntax highlighting fixup automation
m (→‎{{header|Phix}}: syntax coloured, made p2js compatible)
m (syntax highlighting fixup automation)
Line 23:
{{trans|Python}}
 
<langsyntaxhighlight lang="11l">T Node
String sub
[Int] ch
Line 86:
f(0, ‘’)
 
SuffixTree(‘banana$’).visualize()</langsyntaxhighlight>
 
{{out}}
Line 105:
=={{header|C sharp|C#}}==
{{trans|C++}}
<langsyntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
 
Line 214:
}
}
}</langsyntaxhighlight>
{{out}}
<pre>+
Line 230:
=={{header|C++}}==
{{trans|D}}
<langsyntaxhighlight lang="cpp">#include <functional>
#include <iostream>
#include <vector>
Line 334:
int main() {
SuffixTree("banana$").visualize();
}</langsyntaxhighlight>
{{out}}
<pre>+
Line 350:
=={{header|D}}==
{{trans|Kotlin}}
<langsyntaxhighlight Dlang="d">import std.stdio;
 
struct Node {
Line 442:
void main() {
SuffixTree("banana$").visualize();
}</langsyntaxhighlight>
{{out}}
<pre>┐
Line 458:
=={{header|Go}}==
Vis function from [[Visualize_a_tree#Unicode]].
<langsyntaxhighlight lang="go">package main
 
import "fmt"
Line 543:
}
f(0, "")
}</langsyntaxhighlight>
{{out}}
<pre>
Line 563:
Implementation:
 
<langsyntaxhighlight Jlang="j">classify=: {.@> </. ]
 
build_tree=:3 :0
Line 589:
tree=. B=:|:build_tree <\. y
((1+#y)-each {.tree),}.tree
)</langsyntaxhighlight>
 
Task example:
 
<langsyntaxhighlight Jlang="j"> suffix_tree 'banana$'
┌──┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│__│1 │_│_ │2 │4│6│_ │3 │5│7│
Line 600:
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
└──┴───────┴─┴──┴───┴─┴─┴──┴───┴─┴─┘</langsyntaxhighlight>
 
The first row is the leaf number (_ for internal nodes).
Line 610:
Visualizing, using [[Visualize_a_tree#J|showtree]] and prefixing the substring leading to each leaf with the leaf number (in brackets):
 
<langsyntaxhighlight Jlang="j">fmttree=: ;@(1&{) showtree~ {: (,~ }.`('[','] ',~":)@.(_>|))each {.
 
fmttree suffix_tree 'banana$'
Line 620:
├─ na ────────┴─ [5] $
└─ [7] $
</syntaxhighlight>
</lang>
 
=={{header|Java}}==
{{trans|Kotlin}}
<langsyntaxhighlight Javalang="java">import java.util.ArrayList;
import java.util.List;
 
Line 717:
new SuffixTree("banana$").visualize();
}
}</langsyntaxhighlight>
{{out}}
<pre>┐
Line 733:
=={{header|JavaScript}}==
{{trans|Java}}
<langsyntaxhighlight JavaScriptlang="javascript">class Node {
sub = ''; // a substring of the input string
children = []; // list of child nodes
Line 819:
 
const st = new SuffixTree('banana');
console.log(st.toString());</langsyntaxhighlight>
 
{{out}}
Line 834:
=={{header|Julia}}==
{{trans|Go}}
<langsyntaxhighlight lang="julia">import Base.print
 
mutable struct Node
Line 907:
 
println(SuffixTree("banana\$"))
</langsyntaxhighlight> {{out}}
<pre>
┐
Line 924:
=={{header|Kotlin}}==
{{trans|Go}}
<langsyntaxhighlight lang="scala">// version 1.1.3
 
class Node {
Line 1,009:
fun main(args: Array<String>) {
SuffixTree("banana$").visualize()
}</langsyntaxhighlight>
 
{{out}}
Line 1,028:
=={{header|Nim}}==
{{trans|Go}}
<langsyntaxhighlight Nimlang="nim">type
 
Tree = seq[Node]
Line 1,098:
 
 
newTree("banana$").vis()</langsyntaxhighlight>
 
{{out}}
Line 1,115:
=={{header|Perl}}==
{{trans|Raku}}
<langsyntaxhighlight Perllang="perl">use strict;
use warnings;
use Data::Dumper;
Line 1,145:
return $h;
}
print +Dumper suffix_tree suffixes 'banana$';</langsyntaxhighlight>
{{out}}
<pre>$VAR1 = {
Line 1,165:
=={{header|Phix}}==
{{trans|D}}
<!--<langsyntaxhighlight Phixlang="phix">(phixonline)-->
<span style="color: #008080;">with</span> <span style="color: #008080;">javascript_semantics</span>
<span style="color: #000080;font-style:italic;">-- tree nodes are simply {string substr, sequence children_idx}</span>
Line 1,238:
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">SuffixTree</span><span style="color: #0000FF;">(</span><span style="color: #008000;">"banana$"</span><span style="color: #0000FF;">)</span>
<span style="color: #000000;">visualize</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<!--</langsyntaxhighlight>-->
{{out}}
<pre>
Line 1,256:
=={{header|Python}}==
{{trans|D}}
<langsyntaxhighlight lang="python">class Node:
def __init__(self, sub="", children=None):
self.sub = sub
Line 1,322:
f(0, "")
 
SuffixTree("banana$").visualize()</langsyntaxhighlight>
{{out}}
<pre>+-
Line 1,340:
by Danny Yoo for more information on how to use suffix trees in Racket.
 
<langsyntaxhighlight lang="racket">#lang racket
(require (planet dyoo/suffixtree))
(define tree (make-tree))
Line 1,356:
((list c ct ...) (show-node c (string-append dpth " |")) (l ct)))))
 
(show-node (tree-root tree) "")</langsyntaxhighlight>
 
{{out}}
Line 1,378:
The display code is a variant of the [[visualize_a_tree#Raku|visualize a tree]] task code.
 
<syntaxhighlight lang="raku" perl6line>multi suffix-tree(Str $str) { suffix-tree flat map &flip, [\~] $str.flip.comb }
multi suffix-tree(@a) {
hash
Line 1,415:
}
flat visit($tree, $indent xx 2);
}</langsyntaxhighlight>
 
{{out}}
Line 1,432:
=={{header|Sidef}}==
{{trans|Raku}}
<langsyntaxhighlight lang="ruby">func suffix_tree(Str t) {
suffix_tree(^t.len -> map { t.substr(_) })
}
Line 1,456:
}
 
say suffix_tree('banana$')</langsyntaxhighlight>
{{out}}
<pre>
Line 1,478:
=={{header|Wren}}==
{{trans|Kotlin}}
<langsyntaxhighlight lang="ecmascript">class Node {
construct new() {
_sub = "" // a substring of the input string
Line 1,568:
}
 
SuffixTree.new("banana$").visualize()</langsyntaxhighlight>
 
{{out}}
Thundergnat
10,333

edits

Retrieved from "https://rosettacode.org/wiki/Special:MobileDiff/328527"
Cookies help us deliver our services. By using our services, you agree to our use of cookies.
More information