Suffix tree: Difference between revisions
m
→{{header|11l}}: Void
(Added Sidef) |
Alextretyak (talk | contribs) m (→{{header|11l}}: Void) |
||
| (32 intermediate revisions by 13 users not shown) | |||
Line 10:
* No two edges starting out of a node can have string labels beginning with the same character.
* The string obtained by concatenating all the string labels found on the path from the root to leaf i spells out suffix S[i..n], for i from 1 to n.
Such a tree does not exist for all strings. To ensure existence, a character that is not found in S must be appended at its end. The character '$' is traditionally used for this purpose.
Line 18 ⟶ 19:
The computation time for an efficient algorithm should be <math>O(n)</math>, but such an algorithm might be difficult to implement. An easier, <math>O(n^2)</math> algorithm is accepted.
=={{header|11l}}==
{{trans|Python}}
<syntaxhighlight lang="11l">T Node
String sub
[Int] ch
F (sub, children)
.sub = sub
.ch = children
T SuffixTree
nodes = [Node(‘’, [Int]())]
F (str)
L(i) 0 .< str.len
.addSuffix(str[i..])
F addSuffix(suf)
V n = 0
V i = 0
L i < suf.len
V b = suf[i]
V x2 = 0
Int n2
L
V children = .nodes[n].ch
I x2 == children.len
n2 = .nodes.len
.nodes.append(Node(suf[i..], [Int]()))
.nodes[n].ch.append(n2)
R
n2 = children[x2]
I .nodes[n2].sub[0] == b
L.break
x2 = x2 + 1
V sub2 = .nodes[n2].sub
V j = 0
L j < sub2.len
I suf[i + j] != sub2[j]
V n3 = n2
n2 = .nodes.len
.nodes.append(Node(sub2[0 .< j], [n3]))
.nodes[n3].sub = sub2[j..]
.nodes[n].ch[x2] = n2
L.break
j = j + 1
i = i + j
n = n2
F visualize()
I .nodes.empty
print(‘<empty>’)
R
F f(Int n, String pre) -> Void
V children = @.nodes[n].ch
I children.empty
print(‘-- ’(@.nodes[n].sub))
R
print(‘+- ’(@.nodes[n].sub))
L(c) children[0 .< (len)-1]
print(pre‘ +-’, end' ‘ ’)
@f(c, pre‘ | ’)
print(pre‘ +-’, end' ‘ ’)
@f(children.last, pre‘ ’)
f(0, ‘’)
SuffixTree(‘banana$’).visualize()</syntaxhighlight>
{{out}}
<pre>
+-
+- -- banana$
+- +- a
| +- +- na
| | +- -- na$
| | +- -- $
| +- -- $
+- +- na
| +- -- na$
| +- -- $
+- -- $
</pre>
=={{header|C sharp|C#}}==
{{trans|C++}}
<syntaxhighlight lang="csharp">using System;
using System.Collections.Generic;
namespace SuffixTree {
class Node {
public string sub; // a substring of the input string
public List<int> ch = new List<int>(); // vector of child nodes
public Node() {
sub = "";
}
public Node(string sub, params int[] children) {
this.sub = sub;
ch.AddRange(children);
}
}
class SuffixTree {
readonly List<Node> nodes = new List<Node>();
public SuffixTree(string str) {
nodes.Add(new Node());
for (int i = 0; i < str.Length; i++) {
AddSuffix(str.Substring(i));
}
}
public void Visualize() {
if (nodes.Count == 0) {
Console.WriteLine("<empty>");
return;
}
void f(int n, string pre) {
var children = nodes[n].ch;
if (children.Count == 0) {
Console.WriteLine("- {0}", nodes[n].sub);
return;
}
Console.WriteLine("+ {0}", nodes[n].sub);
var it = children.GetEnumerator();
if (it.MoveNext()) {
do {
var cit = it;
if (!cit.MoveNext()) break;
Console.Write("{0}+-", pre);
f(it.Current, pre + "| ");
} while (it.MoveNext());
}
Console.Write("{0}+-", pre);
f(children[children.Count-1], pre+" ");
}
f(0, "");
}
private void AddSuffix(string suf) {
int n = 0;
int i = 0;
while (i < suf.Length) {
char b = suf[i];
int x2 = 0;
int n2;
while (true) {
var children = nodes[n].ch;
if (x2 == children.Count) {
// no matching child, remainder of suf becomes new node
n2 = nodes.Count;
nodes.Add(new Node(suf.Substring(i)));
nodes[n].ch.Add(n2);
return;
}
n2 = children[x2];
if (nodes[n2].sub[0] == b) {
break;
}
x2++;
}
// find prefix of remaining suffix in common with child
var sub2 = nodes[n2].sub;
int j = 0;
while (j < sub2.Length) {
if (suf[i + j] != sub2[j]) {
// split n2
var n3 = n2;
// new node for the part in common
n2 = nodes.Count;
nodes.Add(new Node(sub2.Substring(0, j), n3));
nodes[n3].sub = sub2.Substring(j); // old node loses the part in common
nodes[n].ch[x2] = n2;
break; // continue down the tree
}
j++;
}
i += j; // advance past part in common
n = n2; // continue down the tree
}
}
}
class Program {
static void Main() {
new SuffixTree("banana$").Visualize();
}
}
}</syntaxhighlight>
{{out}}
<pre>+
+-- banana$
+-+ a
| +-+ na
| | +-- na$
| | +-- $
| +-- $
+-+ na
| +-- na$
| +-- $
+-- $</pre>
=={{header|C++}}==
{{trans|D}}
<syntaxhighlight lang="cpp">#include <functional>
#include <iostream>
#include <vector>
struct Node {
std::string sub = ""; // a substring of the input string
std::vector<int> ch; // vector of child nodes
Node() {
// empty
}
Node(const std::string& sub, std::initializer_list<int> children) : sub(sub) {
ch.insert(ch.end(), children);
}
};
struct SuffixTree {
std::vector<Node> nodes;
SuffixTree(const std::string& str) {
nodes.push_back(Node{});
for (size_t i = 0; i < str.length(); i++) {
addSuffix(str.substr(i));
}
}
void visualize() {
if (nodes.size() == 0) {
std::cout << "<empty>\n";
return;
}
std::function<void(int, const std::string&)> f;
f = [&](int n, const std::string & pre) {
auto children = nodes[n].ch;
if (children.size() == 0) {
std::cout << "- " << nodes[n].sub << '\n';
return;
}
std::cout << "+ " << nodes[n].sub << '\n';
auto it = std::begin(children);
if (it != std::end(children)) do {
if (std::next(it) == std::end(children)) break;
std::cout << pre << "+-";
f(*it, pre + "| ");
it = std::next(it);
} while (true);
std::cout << pre << "+-";
f(children[children.size() - 1], pre + " ");
};
f(0, "");
}
private:
void addSuffix(const std::string & suf) {
int n = 0;
size_t i = 0;
while (i < suf.length()) {
char b = suf[i];
int x2 = 0;
int n2;
while (true) {
auto children = nodes[n].ch;
if (x2 == children.size()) {
// no matching child, remainder of suf becomes new node
n2 = nodes.size();
nodes.push_back(Node(suf.substr(i), {}));
nodes[n].ch.push_back(n2);
return;
}
n2 = children[x2];
if (nodes[n2].sub[0] == b) {
break;
}
x2++;
}
// find prefix of remaining suffix in common with child
auto sub2 = nodes[n2].sub;
size_t j = 0;
while (j < sub2.size()) {
if (suf[i + j] != sub2[j]) {
// split n2
auto n3 = n2;
// new node for the part in common
n2 = nodes.size();
nodes.push_back(Node(sub2.substr(0, j), { n3 }));
nodes[n3].sub = sub2.substr(j); // old node loses the part in common
nodes[n].ch[x2] = n2;
break; // continue down the tree
}
j++;
}
i += j; // advance past part in common
n = n2; // continue down the tree
}
}
};
int main() {
SuffixTree("banana$").visualize();
}</syntaxhighlight>
{{out}}
<pre>+
+-- banana$
+-+ a
| +-+ na
| | +-- na$
| | +-- $
| +-- $
+-+ na
| +-- na$
| +-- $
+-- $</pre>
=={{header|D}}==
{{trans|Kotlin}}
<syntaxhighlight lang="d">import std.stdio;
struct Node {
string sub = ""; // a substring of the input string
int[] ch; // array of child nodes
this(string sub, int[] children ...) {
this.sub = sub;
ch = children;
}
}
struct SuffixTree {
Node[] nodes;
this(string str) {
nodes ~= Node();
for (int i=0; i<str.length; ++i) {
addSuffix(str[i..$]);
}
}
private void addSuffix(string suf) {
int n = 0;
int i = 0;
while (i < suf.length) {
char b = suf[i];
int x2 = 0;
int n2;
while (true) {
auto children = nodes[n].ch;
if (x2 == children.length) {
// no matching child, remainder of suf becomes new node.
n2 = nodes.length;
nodes ~= Node(suf[i..$]);
nodes[n].ch ~= n2;
return;
}
n2 = children[x2];
if (nodes[n2].sub[0] == b) {
break;
}
x2++;
}
// find prefix of remaining suffix in common with child
auto sub2 = nodes[n2].sub;
int j = 0;
while (j < sub2.length) {
if (suf[i + j] != sub2[j]) {
// split n2
auto n3 = n2;
// new node for the part in common
n2 = nodes.length;
nodes ~= Node(sub2[0..j], n3);
nodes[n3].sub = sub2[j..$]; // old node loses the part in common
nodes[n].ch[x2] = n2;
break; // continue down the tree
}
j++;
}
i += j; // advance past part in common
n = n2; // continue down the tree
}
}
void visualize() {
if (nodes.length == 0) {
writeln("<empty>");
return;
}
void f(int n, string pre) {
auto children = nodes[n].ch;
if (children.length == 0) {
writefln("╴ %s", nodes[n].sub);
return;
}
writefln("┐ %s", nodes[n].sub);
foreach (c; children[0..$-1]) {
write(pre, "├─");
f(c, pre ~ "│ ");
}
write(pre, "└─");
f(children[$-1], pre ~ " ");
}
f(0, "");
}
}
void main() {
SuffixTree("banana$").visualize();
}</syntaxhighlight>
{{out}}
<pre>┐
├─╴ banana$
├─┐ a
│ ├─┐ na
│ │ ├─╴ na$
│ │ └─╴ $
│ └─╴ $
├─┐ na
│ ├─╴ na$
│ └─╴ $
└─╴ $</pre>
== Elixir ==
<syntaxhighlight lang="elixir">defmodule STree do
defstruct branch: []
defp suffixes([]), do: []
defp suffixes(w), do: [w | suffixes tl(w)]
defp lcp([], _, acc), do: acc
defp lcp(_, [], acc), do: acc
defp lcp([c | u], [a | w], acc) do
if c == a do
lcp(u, w, acc + 1)
else acc
end
end
defp g([], aw), do: [{{aw, length aw}, nil}]
defp g(cusnes, aw) do
[cusn | es] = cusnes
{cus, node} = cusn
{cu, culen} = cus
cpl = case node do
nil -> lcp cu, aw, 0
_ -> lcp (Enum.take cu, culen), aw, 0
end
x = Enum.drop cu, cpl
xlen = culen - cpl
y = Enum.drop aw, cpl
ex = {{x, xlen}, node}
ey = {{y, length y}, nil}
cond do
hd(aw) > hd(cu) -> [cusn | g(es, aw)]
hd(aw) < hd(cu) -> [{{aw, length aw}, nil} | cusnes]
nil != node && xlen == 0 -> [{cus, insert_suffix(y, node)} | es]
hd(x) < hd(y) -> [{{cu, cpl}, %STree{branch: [ex, ey]}} | es]
true -> [{{cu, cpl}, %STree{branch: [ey, ex]}} | es]
end
end
defp insert_suffix(aw, node), do: %STree{branch: g(node.branch, aw)}
def naive_insertion(t), do: List.foldl(suffixes(t), %STree{}, &insert_suffix/2)
defp f(nil, _, label), do: IO.puts("╴ #{label}")
defp f(%STree{branch: children}, pre, label) do
IO.puts "┐ #{label}"
children
|> Enum.take(length(children) - 1)
|> Enum.each(fn c ->
IO.write(pre <> "├─")
{ws, len} = elem(c, 0)
f(elem(c, 1), pre <> "│ ", Enum.join(Enum.take ws, len))
end)
IO.write(pre <> "└─")
c = List.last(children)
{ws, len} = elem(c, 0)
f(elem(c, 1), pre <> " ", Enum.join(Enum.take ws, len))
end
def visualize(n), do: f(n, "", "")
def main do
"banana$"
|> String.graphemes
|> naive_insertion
|> visualize
end
end</syntaxhighlight>
{{out}}
<pre>
┐
├─╴ $
├─┐ a
│ ├─╴ $
│ └─┐ na
│ ├─╴ $
│ └─╴ na$
├─╴ banana$
└─┐ na
├─╴ $
└─╴ na$
</pre>
=={{header|Go}}==
Vis function from [[Visualize_a_tree#Unicode]].
<
import "fmt"
Line 106 ⟶ 627:
}
f(0, "")
}</
{{out}}
<pre>
Line 126 ⟶ 647:
Implementation:
<
build_tree=:3 :0
Line 152 ⟶ 673:
tree=. B=:|:build_tree <\. y
((1+#y)-each {.tree),}.tree
)</
Task example:
<
┌──┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│__│1 │_│_ │2 │4│6│_ │3 │5│7│
Line 163 ⟶ 684:
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
└──┴───────┴─┴──┴───┴─┴─┴──┴───┴─┴─┘</
The first row is the leaf number (_ for internal nodes).
Line 173 ⟶ 694:
Visualizing, using [[Visualize_a_tree#J|showtree]] and prefixing the substring leading to each leaf with the leaf number (in brackets):
<
fmttree suffix_tree 'banana$'
Line 183 ⟶ 704:
├─ na ────────┴─ [5] $
└─ [7] $
</syntaxhighlight>
=={{header|Java}}==
{{trans|Kotlin}}
<syntaxhighlight lang="java">import java.util.ArrayList;
import java.util.List;
public class SuffixTreeProblem {
private static class Node {
String sub = ""; // a substring of the input string
List<Integer> ch = new ArrayList<>(); // list of child nodes
}
private static class SuffixTree {
private List<Node> nodes = new ArrayList<>();
public SuffixTree(String str) {
nodes.add(new Node());
for (int i = 0; i < str.length(); ++i) {
addSuffix(str.substring(i));
}
}
private void addSuffix(String suf) {
int n = 0;
int i = 0;
while (i < suf.length()) {
char b = suf.charAt(i);
List<Integer> children = nodes.get(n).ch;
int x2 = 0;
int n2;
while (true) {
if (x2 == children.size()) {
// no matching child, remainder of suf becomes new node.
n2 = nodes.size();
Node temp = new Node();
temp.sub = suf.substring(i);
nodes.add(temp);
children.add(n2);
return;
}
n2 = children.get(x2);
if (nodes.get(n2).sub.charAt(0) == b) break;
x2++;
}
// find prefix of remaining suffix in common with child
String sub2 = nodes.get(n2).sub;
int j = 0;
while (j < sub2.length()) {
if (suf.charAt(i + j) != sub2.charAt(j)) {
// split n2
int n3 = n2;
// new node for the part in common
n2 = nodes.size();
Node temp = new Node();
temp.sub = sub2.substring(0, j);
temp.ch.add(n3);
nodes.add(temp);
nodes.get(n3).sub = sub2.substring(j); // old node loses the part in common
nodes.get(n).ch.set(x2, n2);
break; // continue down the tree
}
j++;
}
i += j; // advance past part in common
n = n2; // continue down the tree
}
}
public void visualize() {
if (nodes.isEmpty()) {
System.out.println("<empty>");
return;
}
visualize_f(0, "");
}
private void visualize_f(int n, String pre) {
List<Integer> children = nodes.get(n).ch;
if (children.isEmpty()) {
System.out.println("- " + nodes.get(n).sub);
return;
}
System.out.println("┐ " + nodes.get(n).sub);
for (int i = 0; i < children.size() - 1; i++) {
Integer c = children.get(i);
System.out.print(pre + "├─");
visualize_f(c, pre + "│ ");
}
System.out.print(pre + "└─");
visualize_f(children.get(children.size() - 1), pre + " ");
}
}
public static void main(String[] args) {
new SuffixTree("banana$").visualize();
}
}</syntaxhighlight>
{{out}}
<pre>┐
├─- banana$
├─┐ a
│ ├─┐ na
│ │ ├─- na$
│ │ └─- $
│ └─- $
├─┐ na
│ ├─- na$
│ └─- $
└─- $</pre>
=={{header|JavaScript}}==
{{trans|Java}}
<syntaxhighlight lang="javascript">class Node {
sub = ''; // a substring of the input string
children = []; // list of child nodes
}
class SuffixTree {
nodes = [];
constructor(str) {
this.nodes.push(new Node());
for (let i = 0; i < str.length; ++i) {
this.addSuffix(str.slice(i));
}
}
addSuffix(suf) {
let n = 0;
let i = 0;
while (i < suf.length) {
const b = suf.charAt(i);
const children = this.nodes[n].children;
let x2 = 0;
let n2;
while (true) {
if (x2 === children.length) {
// no matching child, remainder of suf becomes new node.
n2 = this.nodes.length;
const temp = new Node();
temp.sub = suf.slice(i);
this.nodes.push(temp);
children.push(n2);
return;
}
n2 = children[x2];
if (this.nodes[n2].sub.charAt(0) === b) break;
x2++;
}
// find prefix of remaining suffix in common with child
const sub2 = this.nodes[n2].sub;
let j = 0;
while (j < sub2.length) {
if (suf.charAt(i + j) !== sub2.charAt(j)) {
// split n2
const n3 = n2;
// new node for the part in common
n2 = this.nodes.length;
const temp = new Node();
temp.sub = sub2.slice(0, j);
temp.children.push(n3);
this.nodes.push(temp);
this.nodes[n3].sub = sub2.slice(j); // old node loses the part in common
this.nodes[n].children[x2] = n2;
break; // continue down the tree
}
j++;
}
i += j; // advance past part in common
n = n2; // continue down the tree
}
}
toString() {
if (this.nodes.length === 0) {
return '<empty>';
}
return this.toString_f(0, '');
}
toString_f(n, pre) {
const children = this.nodes[n].children;
if (children.length === 0) {
return '- ' + this.nodes[n].sub + '\n';
}
let s = '┐ ' + this.nodes[n].sub + '\n';
for (let i = 0; i < children.length - 1; i++) {
const c = children[i];
s += pre + '├─';
s += this.toString_f(c, pre + '│ ');
}
s += pre + '└─';
s += this.toString_f(children[children.length - 1], pre + ' ');
return s;
}
}
const st = new SuffixTree('banana');
console.log(st.toString());</syntaxhighlight>
{{out}}
<pre>
┐
├─- banana
├─┐ a
│ └─┐ na
│ └─- na
└─┐ na
└─- na
</pre>
=={{header|Julia}}==
{{trans|Go}}
<syntaxhighlight lang="julia">import Base.print
mutable struct Node
sub::String
ch::Vector{Int}
Node(str, v=Int[]) = new(str, v)
end
struct SuffixTree
nodes::Vector{Node}
function SuffixTree(s::String)
nod = [Node("", Int[])]
for i in 1:length(s)
addSuffix!(nod, s[i:end])
end
return new(nod)
end
end
function addSuffix!(tree::Vector{Node}, suf::String)
n, i = 1, 1
while i <= length(suf)
x2, n2, b = 1, 1, suf[i]
while true
children = tree[n].ch
if x2 > length(children)
push!(tree, Node(suf[i:end]))
push!(tree[n].ch, length(tree))
return
end
n2 = children[x2]
(tree[n2].sub[1] == b) && break
x2 += 1
end
sub2, j = tree[n2].sub, 0
while j < length(sub2)
if suf[i + j] != sub2[j + 1]
push!(tree, Node(sub2[1:j], [n2]))
tree[n2].sub = sub2[j+1:end]
n2 = length(tree)
tree[n].ch[x2] = n2
break
end
j += 1
end
i += j
n = n2
end
end
function Base.print(io::IO, suffixtree::SuffixTree)
function treeprint(n::Int, pre::String)
children = suffixtree.nodes[n].ch
if isempty(children)
println("╴ ", suffixtree.nodes[n].sub)
else
println("┐ ", suffixtree.nodes[n].sub)
for c in children[1:end-1]
print(pre, "├─")
treeprint(c, pre * "│ ")
end
print(pre, "└─")
treeprint(children[end], pre * " ")
end
end
if isempty(suffixtree.nodes)
println("<empty>")
else
treeprint(1, "")
end
end
println(SuffixTree("banana\$"))
</syntaxhighlight> {{out}}
<pre>
┐
├─╴ banana$
├─┐ a
│ ├─┐ na
│ │ ├─╴ na$
│ │ └─╴ $
│ └─╴ $
├─┐ na
│ ├─╴ na$
│ └─╴ $
└─╴ $
</pre>
=={{header|Kotlin}}==
{{trans|Go}}
<syntaxhighlight lang="scala">// version 1.1.3
class Node {
var sub = "" // a substring of the input string
var ch = mutableListOf<Int>() // list of child nodes
}
class SuffixTree(val str: String) {
val nodes = mutableListOf<Node>(Node())
init {
for (i in 0 until str.length) addSuffix(str.substring(i))
}
private fun addSuffix(suf: String) {
var n = 0
var i = 0
while (i < suf.length) {
val b = suf[i]
val children = nodes[n].ch
var x2 = 0
var n2: Int
while (true) {
if (x2 == children.size) {
// no matching child, remainder of suf becomes new node.
n2 = nodes.size
nodes.add(Node().apply { sub = suf.substring(i) } )
children.add(n2)
return
}
n2 = children[x2]
if (nodes[n2].sub[0] == b) break
x2++
}
// find prefix of remaining suffix in common with child
val sub2 = nodes[n2].sub
var j = 0
while (j < sub2.length) {
if (suf[i + j] != sub2[j]) {
// split n2
val n3 = n2
// new node for the part in common
n2 = nodes.size
nodes.add(Node().apply {
sub = sub2.substring(0, j)
ch.add(n3)
})
nodes[n3].sub = sub2.substring(j) // old node loses the part in common
nodes[n].ch[x2] = n2
break // continue down the tree
}
j++
}
i += j // advance past part in common
n = n2 // continue down the tree
}
}
fun visualize() {
if (nodes.isEmpty()) {
println("<empty>")
return
}
fun f(n: Int, pre: String) {
val children = nodes[n].ch
if (children.isEmpty()) {
println("╴ ${nodes[n].sub}")
return
}
println("┐ ${nodes[n].sub}")
for (c in children.dropLast(1)) {
print(pre + "├─")
f(c, pre + "│ ")
}
print(pre + "└─")
f(children.last(), pre + " ")
}
f(0, "")
}
}
fun main(args: Array<String>) {
SuffixTree("banana$").visualize()
}</syntaxhighlight>
{{out}}
<pre>
┐
├─╴ banana$
├─┐ a
│ ├─┐ na
│ │ ├─╴ na$
│ │ └─╴ $
│ └─╴ $
├─┐ na
│ ├─╴ na$
│ └─╴ $
└─╴ $
</pre>
=={{header|Nim}}==
{{trans|Go}}
<syntaxhighlight lang="nim">type
Tree = seq[Node]
Node = object
sub: string # a substring of the input string.
ch: seq[int] # list of child nodes.
proc addSuffix(t: var Tree; suf: string) =
var n, i = 0
while i < suf.len:
let b = suf[i]
let ch = t[n].ch
var x2, n2: int
while true:
if x2 == ch.len:
# No matching child, remainder of "suf" becomes new node.
n2 = t.len
t.add Node(sub: suf[i..^1])
t[n].ch.add n2
return
n2 = ch[x2]
if t[n2].sub[0] == b: break
inc x2
# Find prefix of remaining suffix in common with child.
let sub2 = t[n2].sub
var j = 0
while j < sub2.len:
if suf[i+j] != sub2[j]:
# Split "sub2".
let n3 = n2
# New node for the part in common.
n2 = t.len
t.add Node(sub: sub2[0..<j], ch: @[n3])
t[n3].sub = sub2[j..^1] # Old node loses the part in common.
t[n].ch[x2] = n2
break # Continue down the tree.
inc j
inc i, j # Advance past part in common.
n = n2 # Continue down the tree.
func newTree(s: string): Tree =
result.add Node() # root node.
for i in 0..s.high:
result.addSuffix s[i..^1]
proc vis(t: Tree) =
if t.len == 0:
echo "<empty>"
return
proc f(n: int; pre: string) =
let children = t[n].ch
if children.len == 0:
echo "╴", t[n].sub
return
echo "┐", t[n].sub
for i in 0..<children.high:
stdout.write pre, "├─"
f(children[i], pre & "│ ")
stdout.write pre, "└─"
f(children[^1], pre & " ")
f(0, "")
newTree("banana$").vis()</syntaxhighlight>
{{out}}
<pre>┐
├─╴banana$
├─┐a
│ ├─┐na
│ │ ├─╴na$
│ │ └─╴$
│ └─╴$
├─┐na
│ ├─╴na$
│ └─╴$
└─╴$</pre>
=={{header|Perl}}==
{{trans|
<
use warnings;
use Data::Dumper;
Line 217 ⟶ 1,229:
return $h;
}
print +Dumper suffix_tree suffixes 'banana$';</
{{out}}
<pre>$VAR1 = {
Line 235 ⟶ 1,247:
};</pre>
=={{header|
{{trans|D}}
<!--<syntaxhighlight lang="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>
<span style="color: #008080;">enum</span> <span style="color: #000000;">SUB</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">=</span><span style="color: #000000;">2</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">addSuffix</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">suffix</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">int</span> <span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">i</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">i</span><span style="color: #0000FF;"><=</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">suffix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">ch</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">suffix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span> <span style="color: #000000;">x2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #000000;">n2</span>
<span style="color: #008080;">while</span> <span style="color: #0000FF;">(</span><span style="color: #004600;">true</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">children</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">x2</span><span style="color: #0000FF;">></span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- no matching child, remainder of suffix becomes new node.</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">suffix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..$],{}})</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">)&</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">n2</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">children</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">][</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]==</span><span style="color: #000000;">ch</span> <span style="color: #008080;">then</span> <span style="color: #008080;">exit</span> <span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">x2</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000080;font-style:italic;">-- find prefix of remaining suffix in common with child</span>
<span style="color: #004080;">string</span> <span style="color: #000000;">prefix</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">]</span>
<span style="color: #004080;">int</span> <span style="color: #000000;">j</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">0</span>
<span style="color: #008080;">while</span> <span style="color: #000000;">j</span><span style="color: #0000FF;"><</span><span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #008080;">if</span> <span style="color: #000000;">suffix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">+</span><span style="color: #000000;">j</span><span style="color: #0000FF;">]!=</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">]</span> <span style="color: #008080;">then</span>
<span style="color: #000080;font-style:italic;">-- split n2: new node for the part in common</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">append</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,{</span><span style="color: #000000;">prefix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..</span><span style="color: #000000;">j</span><span style="color: #0000FF;">],{</span><span style="color: #000000;">n2</span><span style="color: #0000FF;">}})</span>
<span style="color: #000080;font-style:italic;">-- old node loses the part in common</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n2</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">prefix</span><span style="color: #0000FF;">[</span><span style="color: #000000;">j</span><span style="color: #0000FF;">+</span><span style="color: #000000;">1</span><span style="color: #0000FF;">..$]</span>
<span style="color: #000080;font-style:italic;">-- and child idx moves to newly created node</span>
<span style="color: #000000;">n2</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">children</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">deep_copy</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">])</span>
<span style="color: #000000;">children</span><span style="color: #0000FF;">[</span><span style="color: #000000;">x2</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n2</span>
<span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">]</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">children</span>
<span style="color: #008080;">exit</span> <span style="color: #000080;font-style:italic;">-- continue down the tree</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #000000;">j</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">1</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #000000;">i</span> <span style="color: #0000FF;">+=</span> <span style="color: #000000;">j</span> <span style="color: #000080;font-style:italic;">-- advance past part in common</span>
<span style="color: #000000;">n</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">n2</span> <span style="color: #000080;font-style:italic;">-- continue down the tree</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">while</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">function</span> <span style="color: #000000;">SuffixTree</span><span style="color: #0000FF;">(</span><span style="color: #004080;">string</span> <span style="color: #000000;">s</span><span style="color: #0000FF;">)</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #0000FF;">{{</span><span style="color: #008000;">""</span><span style="color: #0000FF;">,{}}}</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">s</span><span style="color: #0000FF;">)</span> <span style="color: #008080;">do</span>
<span style="color: #000000;">t</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">addSuffix</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">,</span><span style="color: #000000;">s</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">..$])</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">return</span> <span style="color: #000000;">t</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">function</span>
<span style="color: #008080;">procedure</span> <span style="color: #000000;">visualize</span><span style="color: #0000FF;">(</span><span style="color: #004080;">sequence</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">integer</span> <span style="color: #000000;">n</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span> <span style="color: #004080;">string</span> <span style="color: #000000;">pre</span><span style="color: #0000FF;">=</span><span style="color: #008000;">""</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">t</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"<empty>\n"</span><span style="color: #0000FF;">);</span>
<span style="color: #008080;">return</span><span style="color: #0000FF;">;</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #004080;">sequence</span> <span style="color: #000000;">children</span> <span style="color: #0000FF;">=</span> <span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">CHILDREN</span><span style="color: #0000FF;">]</span>
<span style="color: #008080;">if</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">)=</span><span style="color: #000000;">0</span> <span style="color: #008080;">then</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"- %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">]})</span>
<span style="color: #008080;">return</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">if</span>
<span style="color: #7060A8;">printf</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #008000;">"+ %s\n"</span><span style="color: #0000FF;">,</span> <span style="color: #0000FF;">{</span><span style="color: #000000;">t</span><span style="color: #0000FF;">[</span><span style="color: #000000;">n</span><span style="color: #0000FF;">][</span><span style="color: #000000;">SUB</span><span style="color: #0000FF;">]})</span>
<span style="color: #004080;">integer</span> <span style="color: #000000;">l</span> <span style="color: #0000FF;">=</span> <span style="color: #7060A8;">length</span><span style="color: #0000FF;">(</span><span style="color: #000000;">children</span><span style="color: #0000FF;">)</span>
<span style="color: #008080;">for</span> <span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">1</span> <span style="color: #008080;">to</span> <span style="color: #000000;">l</span> <span style="color: #008080;">do</span>
<span style="color: #7060A8;">puts</span><span style="color: #0000FF;">(</span><span style="color: #000000;">1</span><span style="color: #0000FF;">,</span><span style="color: #000000;">pre</span><span style="color: #0000FF;">&</span><span style="color: #008000;">"+-"</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><span style="color: #000000;">children</span><span style="color: #0000FF;">[</span><span style="color: #000000;">i</span><span style="color: #0000FF;">],</span><span style="color: #000000;">pre</span><span style="color: #0000FF;">&</span><span style="color: #008080;">iff</span><span style="color: #0000FF;">(</span><span style="color: #000000;">i</span><span style="color: #0000FF;">=</span><span style="color: #000000;">l</span><span style="color: #0000FF;">?</span><span style="color: #008000;">" "</span><span style="color: #0000FF;">:</span><span style="color: #008000;">"| "</span><span style="color: #0000FF;">))</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">for</span>
<span style="color: #008080;">end</span> <span style="color: #008080;">procedure</span>
<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>
<!--</syntaxhighlight>-->
{{out}}
<pre>
+
+-- banana$
+-+ a
| +-+ na
| | +-- na$
| | +-- $
| +-- $
+-+ na
| +-- na$
| +-- $
+-- $
</pre>
=={{header|Python}}==
{{trans|D}}
<syntaxhighlight lang="python">class Node:
def __init__(self, sub="", children=None):
self.sub = sub
self.ch = children or []
class SuffixTree:
def __init__(self, str):
self.nodes = [Node()]
def addSuffix(self, suf):
n = 0
i = 0
while i < len(suf):
b = suf[i]
x2 = 0
while True:
children = self.nodes[n].ch
if x2 == len(children):
# no matching child, remainder of suf becomes new node
n2 = len(self.nodes)
self.nodes.append(Node(suf[i:], []))
self.nodes[n].ch.append(n2)
return
n2 = children[x2]
if self.nodes[n2].sub[0] == b:
break
x2 = x2 + 1
# find prefix of remaining suffix in common with child
sub2 = self.nodes[n2].sub
j = 0
while j < len(sub2):
if suf[i + j] != sub2[j]:
# split n2
n3 = n2
# new node for the part in common
n2 = len(self.nodes)
self.nodes.append(Node(sub2[:j], [n3]))
self.nodes[n3].sub = sub2[j:] # old node loses the part in common
self.nodes[n].ch[x2] = n2
break # continue down the tree
j = j + 1
i = i + j # advance past part in common
n = n2 # continue down the tree
def visualize(self):
if len(self.nodes) == 0:
print "<empty>"
return
def f(n, pre):
children = self.nodes[n].ch
if len(children) == 0:
print "--", self.nodes[n].sub
return
print "+-", self.nodes[n].sub
for c in children[:-1]:
print pre, "+-",
f(c, pre + " | ")
print pre, "+-",
f(children[-1], pre + " ")
f(0, "")
SuffixTree("banana$").visualize()</syntaxhighlight>
{{out}}
<pre>
+- -- banana$
+- +- a
| +- +- na
| | +- -- na$
| | +- -- $
| +- -- $
+- +- na
| +- -- na$
| +- -- $
=={{header|Racket}}==
Line 276 ⟶ 1,424:
by Danny Yoo for more information on how to use suffix trees in Racket.
<
(require (planet dyoo/suffixtree))
(define tree (make-tree))
Line 292 ⟶ 1,440:
((list c ct ...) (show-node c (string-append dpth " |")) (l ct)))))
(show-node (tree-root tree) "")</
{{out}}
Line 306 ⟶ 1,454:
| `-- na$
`-- banana$</pre>
=={{header|Raku}}==
(formerly Perl 6)
{{Works with|Rakudo|2018.04}}
Here is quite a naive algorithm, probably <math>O(n^2)</math>.
The display code is a variant of the [[visualize_a_tree#Raku|visualize a tree]] task code.
<syntaxhighlight lang="raku" line>multi suffix-tree(Str $str) { suffix-tree flat map &flip, [\~] $str.flip.comb }
multi suffix-tree(@a) {
hash
@a == 0 ?? () !!
@a == 1 ?? ( @a[0] => [] ) !!
gather for @a.classify(*.substr(0, 1)) {
my $subtree = suffix-tree(grep *.chars, map *.substr(1), .value[]);
if $subtree == 1 {
my $pair = $subtree.pick;
take .key ~ $pair.key => $pair.value;
} else {
take .key => $subtree;
}
}
}
my $tree = root => suffix-tree 'banana$';
.say for visualize-tree $tree, *.key, *.value.List;
sub visualize-tree($tree, &label, &children,
:$indent = '',
:@mid = ('├─', '│ '),
:@end = ('└─', ' '),
) {
sub visit($node, *@pre) {
gather {
take @pre[0] ~ $node.&label;
my @children = sort $node.&children;
my $end = @children.end;
for @children.kv -> $_, $child {
when $end { take visit($child, (@pre[1] X~ @end)) }
default { take visit($child, (@pre[1] X~ @mid)) }
}
}
}
flat visit($tree, $indent xx 2);
}</syntaxhighlight>
{{out}}
<pre>root
├─$
├─a
│ ├─$
│ └─na
│ ├─$
│ └─na$
├─banana$
└─na
├─$
└─na$</pre>
=={{header|Sidef}}==
{{trans|
<
suffix_tree(^t.len -> map { t.substr(_) })
}
func suffix_tree(a {.
}
func suffix_tree(Arr a) {
Line 332 ⟶ 1,540:
}
say suffix_tree('banana$')</
{{out}}
<pre>
Hash(
"$" =>
"a" => Hash(
"$" =>
"na" => Hash(
"$" =>
"na$" =>
)
),
"banana$" =>
"na" => Hash(
"$" =>
"na$" =>
)
)
</pre>
=={{header|Wren}}==
{{trans|Kotlin}}
<syntaxhighlight lang="wren">class Node {
construct new() {
_sub = "" // a substring of the input string
_ch = [] // list of child nodes
}
sub { _sub }
ch { _ch }
sub=(s) { _sub = s }
}
class SuffixTree {
construct new(str) {
_nodes = [Node.new()]
for (i in 0...str.count) addSuffix_(str[i..-1])
}
addSuffix_(suf) {
var n = 0
var i = 0
while (i < suf.count) {
var b = suf[i]
var children = _nodes[n].ch
var x2 = 0
var n2
while (true) {
if (x2 == children.count) {
// no matching child, remainder of suf becomes new node.
n2 = _nodes.count
var nd = Node.new()
nd.sub = suf[i..-1]
_nodes.add(nd)
children.add(n2)
return
}
n2 = children[x2]
if (_nodes[n2].sub[0] == b) break
x2 = x2 + 1
}
// find prefix of remaining suffix in common with child
var sub2 = _nodes[n2].sub
var j = 0
while (j < sub2.count) {
if (suf[i + j] != sub2[j]) {
// split n2
var n3 = n2
// new node for the part in common
n2 = _nodes.count
var nd = Node.new()
nd.sub = sub2[0...j]
nd.ch.add(n3)
_nodes.add(nd)
_nodes[n3].sub = sub2[j..-1] // old node loses the part in common
_nodes[n].ch[x2] = n2
break // continue down the tree
}
j = j + 1
}
i = i + j // advance past part in common
n = n2 // continue down the tree
}
}
visualize() {
if (_nodes.isEmpty) {
System.print("<empty>")
return
}
var f // recursive closure
f = Fn.new { |n, pre|
var children = _nodes[n].ch
if (children.isEmpty) {
System.print("╴ %(_nodes[n].sub)")
return
}
System.print("┐ %(_nodes[n].sub)")
for (c in children[0...-1]) {
System.write(pre + "├─")
f.call(c, pre + "│ ")
}
System.write(pre + "└─")
f.call(children[-1], pre + " ")
}
f.call(0, "")
}
}
SuffixTree.new("banana$").visualize()</syntaxhighlight>
{{out}}
<pre>
┐
├─╴ banana$
├─┐ a
│ ├─┐ na
│ │ ├─╴ na$
│ │ └─╴ $
│ └─╴ $
├─┐ na
│ ├─╴ na$
│ └─╴ $
└─╴ $
</pre>
| |||