Suffix tree
A suffix tree is a data structure commonly used in string algorithms.
Suffix tree is a draft programming task. It is not yet considered ready to be promoted as a complete task, for reasons that should be found in its talk page.
Given a string S of length n, its suffix tree is a tree T such that:
- T has exactly n leaves numbered from 1 to n.
- Except for the root, every internal node has at least two children.
- Each edge of T is labelled with a non-empty substring of S.
- 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.
For this task, build and display the suffix tree of the string "banana$". Displaying the tree can be done using the code from the visualize a tree task, but any other convenient method is accepted.
There are several ways to implement the tree data structure, for instance how edges should be labelled. Latitude is given in this matter, but notice that a simple way to do it is to label each node with the label of the edge leading to it.
The computation time for an efficient algorithm should be , but such an algorithm might be difficult to implement. An easier, algorithm is accepted.
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()- Output:
+- +- -- banana$ +- +- a | +- +- na | | +- -- na$ | | +- -- $ | +- -- $ +- +- na | +- -- na$ | +- -- $ +- -- $
with Ada.Text_IO; use Ada.Text_IO;
with Generic_Directed_Weighted_Graph;
with Generic_Address_Order;
procedure Suffix_Tree is
type Node_Type is null record; -- Nodes have no contents
type Default is access Node_Type; -- Default access type
--
-- Node_Order -- Ordering of nodes by their addresses
--
package Node_Order is new Generic_Address_Order (Node_Type);
use Node_Order;
--
-- Ordering of the edge weights
--
function Equal (Left, Right : access String) return Boolean is
begin
return Left.all = Right.all;
end Equal;
function Less (Left, Right : access String) return Boolean is
begin
return Left.all < Right.all;
end Less;
--
-- Directed graph of Node_Type weighted by Character values
--
package Character_Weighted_Graphs is
new Generic_Directed_Weighted_Graph
( Node_Type => Node_Type,
Weight_Type => String,
Pool => Default'Storage_Pool,
Minimal_Parents_Size => 1
);
use Character_Weighted_Graphs;
subtype Suffix_Tree is Character_Weighted_Graphs.Node;
--
-- Print -- Outputs a tree
--
procedure Print (Tree : Suffix_Tree; Prefix : String := "") is
begin
for Index in 1..Get_Children_Number (Tree) loop
Put_Line (Prefix & "|_" & Get_Weight (Tree, Index));
if Index < Get_Children_Number (Tree) then
Print (Get_Child (Tree, Index), Prefix & "| ");
else
Print (Get_Child (Tree, Index), Prefix & " ");
end if;
end loop;
end Print;
--
-- Join -- Merge consequtive signle descendant nodes
--
procedure Join (Parent : Node; Child : in out Node) is
This : Node;
begin
for Index in 1..Get_Children_Number (Child) loop
This := Get_Child (Child, Index);
Join (Child, This);
end loop;
if Get_Children_Number (Child) = 1 then
declare
Weight : constant String := Get_Weight (Parent, Child) &
Get_Weight (Child, This);
begin
Delete (Child, Self);
Connect (Parent, This, Weight);
Child := This;
end;
end if;
end Join;
--
-- Build -- Creates the suffix tree from a string
--
function Build (Text : String) return Suffix_Tree is
Root : Node := new Node_Type;
Focus : Node;
Lower : Natural;
Upper : Natural;
begin
for Index in Text'Range loop
Focus := Root;
for Current in Index..Text'Last loop
Classify (Focus, Text (Current..Current), Lower, Upper);
if Lower = Upper then
Focus := Get_Child (Focus, Lower);
else
declare
Branch : constant Node := new Node_Type;
begin
Connect (Focus, Branch, Text (Current..Current));
Focus := Branch;
end;
end if;
end loop;
end loop;
for Index in 1..Get_Children_Number (Root) loop
Focus := Get_Child (Root, Index);
Join (Root, Focus);
end loop;
return Root;
end Build;
Tree : Suffix_Tree := Build ("banana$");
begin
Print (Tree);
Delete (Tree);
end Suffix_Tree;
The tree is represented by a directed weighted graph. Node weights of the graph are strings. Consequent single child nodes are merged. Weights are ordered by their values.
- Output:
|_$ |_a | |_$ | |_na | |_$ | |_na$ |_banana$ |_na |_$ |_na$
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();
}
}
}
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $
#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();
}
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $
IDENTIFICATION DIVISION.
PROGRAM-ID. SuffixTreeProblem.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 GLOBAL-DATA IS EXTERNAL.
05 NODE-COUNT PIC 9(4).
05 NODES-ARRAY OCCURS 1000 TIMES.
10 SUB-LEN PIC 9(3).
10 SUB-VAL PIC X(100).
10 CHILD-COUNT PIC 9(3).
10 CHILD-ARRAY OCCURS 100 TIMES.
15 CHILD-NODE-IDX PIC 9(4).
01 WS-STR PIC X(100).
01 WS-STR-LEN PIC 9(3).
01 WS-I PIC 9(3).
01 WS-SUF PIC X(100).
01 WS-SUF-LEN PIC 9(3).
PROCEDURE DIVISION.
MAIN-PROCEDURE.
MOVE "banana$" TO WS-STR
MOVE 7 TO WS-STR-LEN
*> Initialize root node
MOVE 1 TO NODE-COUNT
MOVE 0 TO SUB-LEN(1)
MOVE SPACES TO SUB-VAL(1)
MOVE 0 TO CHILD-COUNT(1)
PERFORM VARYING WS-I FROM 1 BY 1 UNTIL WS-I > WS-STR-LEN
MOVE SPACES TO WS-SUF
COMPUTE WS-SUF-LEN = WS-STR-LEN - WS-I + 1
MOVE WS-STR(WS-I : WS-SUF-LEN) TO WS-SUF(1 : WS-SUF-LEN)
CALL "addSuffix" USING WS-SUF WS-SUF-LEN
END-PERFORM
CALL "visualize"
STOP RUN.
END PROGRAM SuffixTreeProblem.
IDENTIFICATION DIVISION.
PROGRAM-ID. addSuffix.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 GLOBAL-DATA IS EXTERNAL.
05 NODE-COUNT PIC 9(4).
05 NODES-ARRAY OCCURS 1000 TIMES.
10 SUB-LEN PIC 9(3).
10 SUB-VAL PIC X(100).
10 CHILD-COUNT PIC 9(3).
10 CHILD-ARRAY OCCURS 100 TIMES.
15 CHILD-NODE-IDX PIC 9(4).
01 N PIC 9(4).
01 I PIC 9(3).
01 B PIC X.
01 X2 PIC 9(3).
01 N2 PIC 9(4).
01 N3 PIC 9(4).
01 SUB2 PIC X(100).
01 SUB2-LEN PIC 9(3).
01 J PIC 9(3).
01 MATCH-FOUND PIC X.
LINKAGE SECTION.
01 L-SUF PIC X(100).
01 L-SUF-LEN PIC 9(3).
PROCEDURE DIVISION USING L-SUF L-SUF-LEN.
MAIN-LOGIC.
MOVE 1 TO N
MOVE 1 TO I
PERFORM UNTIL I > L-SUF-LEN
MOVE L-SUF(I:1) TO B
MOVE 1 TO X2
MOVE 'N' TO MATCH-FOUND
PERFORM FOREVER
IF X2 > CHILD-COUNT(N)
*> no matching child, remainder suf to new node
ADD 1 TO NODE-COUNT
MOVE NODE-COUNT TO N2
MOVE 0 TO CHILD-COUNT(N2)
COMPUTE SUB-LEN(N2) = L-SUF-LEN - I + 1
MOVE L-SUF(I : SUB-LEN(N2))
TO SUB-VAL(N2)(1 : SUB-LEN(N2))
ADD 1 TO CHILD-COUNT(N)
MOVE N2 TO CHILD-NODE-IDX(N, CHILD-COUNT(N))
GOBACK
END-IF
MOVE CHILD-NODE-IDX(N, X2) TO N2
IF SUB-VAL(N2)(1:1) = B
MOVE 'Y' TO MATCH-FOUND
EXIT PERFORM
END-IF
ADD 1 TO X2
END-PERFORM
*> find prefix of remaining suffix in common with child
MOVE SUB-VAL(N2) TO SUB2
MOVE SUB-LEN(N2) TO SUB2-LEN
MOVE 1 TO J
MOVE 'Y' TO MATCH-FOUND
PERFORM UNTIL J > SUB2-LEN
IF L-SUF(I + J - 1 : 1) NOT = SUB2(J : 1)
*> split n2
MOVE N2 TO N3
ADD 1 TO NODE-COUNT
MOVE NODE-COUNT TO N2
MOVE 0 TO CHILD-COUNT(N2)
*> temp.sub = sub2.substring(0, j)
COMPUTE SUB-LEN(N2) = J - 1
IF SUB-LEN(N2) > 0
MOVE SPACES TO SUB-VAL(N2)
MOVE SUB2(1 : SUB-LEN(N2))
TO SUB-VAL(N2)(1 : SUB-LEN(N2))
ELSE
MOVE SPACES TO SUB-VAL(N2)
END-IF
*> temp.ch.add(n3)
ADD 1 TO CHILD-COUNT(N2)
MOVE N3 TO CHILD-NODE-IDX(N2, CHILD-COUNT(N2))
*> nodes.get(n3).sub = sub2.substring(j)
COMPUTE SUB-LEN(N3) = SUB2-LEN - J + 1
MOVE SPACES TO SUB-VAL(N3)
MOVE SUB2(J : SUB-LEN(N3))
TO SUB-VAL(N3)(1 : SUB-LEN(N3))
*> nodes.get(n).ch.set(x2, n2)
MOVE N2 TO CHILD-NODE-IDX(N, X2)
MOVE 'N' TO MATCH-FOUND
EXIT PERFORM
END-IF
ADD 1 TO J
END-PERFORM
COMPUTE I = I + J - 1
MOVE N2 TO N
END-PERFORM.
GOBACK.
END PROGRAM addSuffix.
IDENTIFICATION DIVISION.
PROGRAM-ID. visualize.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 GLOBAL-DATA IS EXTERNAL.
05 NODE-COUNT PIC 9(4).
05 NODES-ARRAY OCCURS 1000 TIMES.
10 SUB-LEN PIC 9(3).
10 SUB-VAL PIC X(100).
10 CHILD-COUNT PIC 9(3).
10 CHILD-ARRAY OCCURS 100 TIMES.
15 CHILD-NODE-IDX PIC 9(4).
01 INIT-PRE PIC X(1000) VALUE SPACES.
01 INIT-PRE-LEN PIC 9(4) VALUE 0.
01 ROOT-IDX PIC 9(4) VALUE 1.
PROCEDURE DIVISION.
MAIN-LOGIC.
IF NODE-COUNT = 0
DISPLAY "<empty>"
GOBACK
END-IF
MOVE 0 TO INIT-PRE-LEN
CALL "visualize_f" USING BY CONTENT ROOT-IDX
BY REFERENCE INIT-PRE
BY CONTENT INIT-PRE-LEN
GOBACK.
END PROGRAM visualize.
IDENTIFICATION DIVISION.
PROGRAM-ID. visualize_f IS RECURSIVE.
DATA DIVISION.
WORKING-STORAGE SECTION.
01 GLOBAL-DATA IS EXTERNAL.
05 NODE-COUNT PIC 9(4).
05 NODES-ARRAY OCCURS 1000 TIMES.
10 SUB-LEN PIC 9(3).
10 SUB-VAL PIC X(100).
10 CHILD-COUNT PIC 9(3).
10 CHILD-ARRAY OCCURS 100 TIMES.
15 CHILD-NODE-IDX PIC 9(4).
LOCAL-STORAGE SECTION.
01 I PIC 9(3).
01 C-IDX PIC 9(4).
01 LAST-CHILD-IDX PIC 9(4).
01 NEXT-PRE PIC X(1000).
01 NEXT-PRE-LEN PIC 9(4).
01 PTR PIC 9(4).
LINKAGE SECTION.
01 L-N PIC 9(4).
01 L-PRE PIC X(1000).
01 L-PRE-LEN PIC 9(4).
PROCEDURE DIVISION USING L-N L-PRE L-PRE-LEN.
MAIN-LOGIC.
IF CHILD-COUNT(L-N) = 0
IF SUB-LEN(L-N) > 0
DISPLAY "- " SUB-VAL(L-N)(1:SUB-LEN(L-N))
ELSE
DISPLAY "- "
END-IF
GOBACK
END-IF
IF SUB-LEN(L-N) > 0
DISPLAY "+ " SUB-VAL(L-N)(1:SUB-LEN(L-N))
ELSE
DISPLAY "+ "
END-IF
COMPUTE LAST-CHILD-IDX = CHILD-COUNT(L-N) - 1
PERFORM VARYING I FROM 1 BY 1 UNTIL I > LAST-CHILD-IDX
MOVE CHILD-NODE-IDX(L-N, I) TO C-IDX
IF L-PRE-LEN > 0
DISPLAY L-PRE(1:L-PRE-LEN) "+-" WITH NO ADVANCING
ELSE
DISPLAY "+-" WITH NO ADVANCING
END-IF
MOVE SPACES TO NEXT-PRE
MOVE 1 TO PTR
IF L-PRE-LEN > 0
STRING L-PRE(1:L-PRE-LEN) DELIMITED BY SIZE
"| " DELIMITED BY SIZE
INTO NEXT-PRE
WITH POINTER PTR
ELSE
STRING "| " DELIMITED BY SIZE
INTO NEXT-PRE
WITH POINTER PTR
END-IF
COMPUTE NEXT-PRE-LEN = PTR - 1
CALL "visualize_f" USING BY CONTENT C-IDX
BY REFERENCE NEXT-PRE
BY CONTENT NEXT-PRE-LEN
END-PERFORM
MOVE CHILD-NODE-IDX(L-N, CHILD-COUNT(L-N)) TO C-IDX
IF L-PRE-LEN > 0
DISPLAY L-PRE(1:L-PRE-LEN) "+-" WITH NO ADVANCING
ELSE
DISPLAY "+-" WITH NO ADVANCING
END-IF
MOVE SPACES TO NEXT-PRE
MOVE 1 TO PTR
IF L-PRE-LEN > 0
STRING L-PRE(1:L-PRE-LEN) DELIMITED BY SIZE
" " DELIMITED BY SIZE
INTO NEXT-PRE
WITH POINTER PTR
ELSE
STRING " " DELIMITED BY SIZE
INTO NEXT-PRE
WITH POINTER PTR
END-IF
COMPUTE NEXT-PRE-LEN = PTR - 1
CALL "visualize_f" USING BY CONTENT C-IDX
BY REFERENCE NEXT-PRE
BY CONTENT NEXT-PRE-LEN
GOBACK.
END PROGRAM visualize_f.
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $
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 = cast(int) 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 = cast(int) 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();
}
- Output:
┐ ├─╴ banana$ ├─┐ a │ ├─┐ na │ │ ├─╴ na$ │ │ └─╴ $ │ └─╴ $ ├─┐ na │ ├─╴ na$ │ └─╴ $ └─╴ $
import 'dart:io';
class Node {
String sub = "";
List<int> ch = [];
}
class SuffixTree {
List<Node> nodes = [];
SuffixTree(String str) {
nodes.add(Node());
for (int i = 0; i < str.length; i++) {
addSuffix(str.substring(i));
}
}
void addSuffix(String suf) {
int n = 0;
int i = 0;
while (i < suf.length) {
String b = suf[i];
List<int> children = nodes[n].ch;
int x2 = 0;
int n2;
while (true) {
if (x2 == children.length) {
// no matching child, remainder of suf becomes new node.
n2 = nodes.length;
Node temp = Node();
temp.sub = suf.substring(i);
nodes.add(temp);
children.add(n2);
return;
}
n2 = children[x2];
if (nodes[n2].sub[0] == b) break;
x2++;
}
// find prefix of remaining suffix in common with child
String sub2 = nodes[n2].sub;
int j = 0;
while (j < sub2.length) {
if (suf[i + j] != sub2[j]) {
// split n2
int n3 = n2;
// new node for the part in common
n2 = nodes.length;
Node temp = Node();
temp.sub = sub2.substring(0, j);
temp.ch.add(n3);
nodes.add(temp);
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
}
}
void visualize() {
if (nodes.isEmpty) {
print("<empty>");
return;
}
visualizeF(0, "");
}
void visualizeF(int n, String pre) {
List<int> children = nodes[n].ch;
if (children.isEmpty) {
print("- ${nodes[n].sub}");
return;
}
print("┐ ${nodes[n].sub}");
for (int i = 0; i < children.length - 1; i++) {
int c = children[i];
stdout.write("$pre├─");
visualizeF(c, "$pre│ ");
}
stdout.write("$pre└─");
visualizeF(children[children.length - 1], "$pre ");
}
}
void main() {
SuffixTree("banana\$").visualize();
}
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
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
- Output:
┐ ├─╴ $ ├─┐ a │ ├─╴ $ │ └─┐ na │ ├─╴ $ │ └─╴ na$ ├─╴ banana$ └─┐ na ├─╴ $ └─╴ na$
Type TipoNodo
texto As String
numHijos As Integer
hijos(100) As Integer
End Type
Type TipoArbolSufijo
numNodos As Integer
nodos(1000) As TipoNodo
Declare Sub inicializar()
Declare Sub agregarSufijo(sufijo As String)
Declare Sub visualizar()
Declare Sub visualizarNodo(n As Integer, prefijo As String)
End Type
Sub TipoArbolSufijo.inicializar()
numNodos = 1
nodos(0).texto = ""
nodos(0).numHijos = 0
End Sub
Sub TipoArbolSufijo.agregarSufijo(sufijo As String)
Dim As Integer n = 0, i = 0
Do While i < Len(sufijo)
Dim As String b = Mid(sufijo, i + 1, 1)
Dim As Integer x2 = 0, n2
Do
If x2 >= nodos(n).numHijos Then
n2 = numNodos
numNodos += 1
nodos(n2).texto = Mid(sufijo, i + 1)
nodos(n2).numHijos = 0
nodos(n).numHijos += 1
nodos(n).hijos(x2) = n2
Exit Sub
End If
n2 = nodos(n).hijos(x2)
If Left(nodos(n2).texto, 1) = b Then Exit Do
x2 += 1
Loop
Dim As String sub2 = nodos(n2).texto
Dim As Integer j = 0
Do While j < Len(sub2)
If Mid(sufijo, i + j + 1, 1) <> Mid(sub2, j + 1, 1) Then
Dim As Integer n3 = n2
n2 = numNodos
numNodos += 1
nodos(n2).texto = Left(sub2, j)
nodos(n3).texto = Mid(sub2, j + 1)
nodos(n2).numHijos = 1
nodos(n2).hijos(0) = n3
nodos(n).hijos(x2) = n2
Exit Do
End If
j += 1
Loop
i += j
n = n2
Loop
End Sub
Sub TipoArbolSufijo.visualizar()
If numNodos = 0 Then
Print "<vacío>"
Exit Sub
End If
visualizarNodo(0, "")
End Sub
Sub TipoArbolSufijo.visualizarNodo(n As Integer, prefijo As String)
If nodos(n).numHijos = 0 Then
Print "-- " & nodos(n).texto
Exit Sub
End If
Print "+- " & nodos(n).texto
For i As Integer = 0 To nodos(n).numHijos - 2
Print prefijo & " +-";
visualizarNodo(nodos(n).hijos(i), prefijo & " | ")
Next
Print prefijo & " +-";
visualizarNodo(nodos(n).hijos(nodos(n).numHijos - 1), prefijo & " ")
End Sub
' Main program
Dim As TipoArbolSufijo arbol
arbol.inicializar()
Dim As String texto = "banana$"
For i As Integer = 1 To Len(texto)
arbol.agregarSufijo(Mid(texto, i))
Next
arbol.visualizar()
Sleep
- Output:
+- +--- banana$ +-+- a | +-+- na | | +--- na$ | | +--- $ | +--- $ +-+- na | +--- na$ | +--- $ +--- $
Vis function from Visualize_a_tree#Unicode.
package main
import "fmt"
func main() {
vis(buildTree("banana$"))
}
type tree []node
type node struct {
// a substring of the input string
sub string
// list of child nodes
ch []int
}
func buildTree(s string) tree {
// root node
t := tree{node{}}
for i := range s {
t = t.addSuffix(s[i:])
}
return t
}
func (t tree) addSuffix(suf string) tree {
n := 0
for i := 0; i < len(suf); {
b := suf[i]
ch := t[n].ch
var x2, n2 int
for ; ; x2++ {
if x2 == len(ch) {
// no matching child, remainder of suf becomes new node.
n2 = len(t)
t = append(t, node{sub: suf[i:]})
t[n].ch = append(t[n].ch, n2)
return t
}
n2 = ch[x2]
if t[n2].sub[0] == b {
break
}
}
// find prefix of remaining suffix in common with child
sub2 := t[n2].sub
j := 0
for ; j < len(sub2); j++ {
if suf[i+j] != sub2[j] {
// split n2
n3 := n2
// new node for the part in common
n2 = len(t)
t = append(t, node{sub2[:j], []int{n3}})
// old node loses the part in common
t[n3].sub = sub2[j:]
t[n].ch[x2] = n2
// continue down the tree
break
}
}
// advance past part in common
i += j
// continue down the tree
n = n2
}
return t
}
func vis(t tree) {
if len(t) == 0 {
fmt.Println("<empty>")
return
}
var f func(int, string)
f = func(n int, pre string) {
children := t[n].ch
if len(children) == 0 {
fmt.Println("╴", t[n].sub)
return
}
fmt.Println("┐", t[n].sub)
last := len(children) - 1
for _, ch := range children[:last] {
fmt.Print(pre, "├─")
f(ch, pre+"│ ")
}
fmt.Print(pre, "└─")
f(children[last], pre+" ")
}
f(0, "")
}
- Output:
┐ ├─╴ banana$ ├─┐ a │ ├─┐ na │ │ ├─╴ na$ │ │ └─╴ $ │ └─╴ $ ├─┐ na │ ├─╴ na$ │ └─╴ $ └─╴ $
Implementation:
classify=: {.@> </. ]
build_tree=:3 :0
tree=. ,:_;_;''
if. 0=#y do. tree return.end.
if. 1=#y do. tree,(#;y);0;y return.end.
for_box.classify y do.
char=. {.>{.>box
subtree=. }.build_tree }.each>box
ndx=.I.0=1&{::"1 subtree
n=.#tree
if. 1=#ndx do.
counts=. 1 + 0&{::"1 subtree
parents=. (n-1) (+*]&*) 1&{::"1 subtree
edges=. (ndx}~ <@(char,ndx&{::)) 2&{"1 subtree
tree=. tree, counts;"0 1 parents;"0 edges
else.
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
)
Task example:
suffix_tree 'banana$'
┌──┬───────┬─┬──┬───┬─┬─┬──┬───┬─┬─┐
│__│1 │_│_ │2 │4│6│_ │3 │5│7│
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│_ │0 │0│2 │3 │3│2│0 │7 │7│0│
├──┼───────┼─┼──┼───┼─┼─┼──┼───┼─┼─┤
│ │banana$│a│na│na$│$│$│na│na$│$│$│
└──┴───────┴─┴──┴───┴─┴─┴──┴───┴─┴─┘
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).
Visualizing, using showtree and prefixing the substring leading to each leaf with the leaf number (in brackets):
fmttree=: ;@(1&{) showtree~ {: (,~ }.`('[','] ',~":)@.(_>|))each {.
fmttree suffix_tree 'banana$'
┌─ [1] banana$
│ ┌─ [2] na$
│ ┌─ na ────┴─ [4] $
────┼─ a ─────────┴─ [6] $
│ ┌─ [3] na$
├─ na ────────┴─ [5] $
└─ [7] $
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();
}
}
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
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());
- Output:
┐ ├─- banana ├─┐ a │ └─┐ na │ └─- na └─┐ na └─- na
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\$"))
- Output:
┐ ├─╴ banana$ ├─┐ a │ ├─┐ na │ │ ├─╴ na$ │ │ └─╴ $ │ └─╴ $ ├─┐ na │ ├─╴ na$ │ └─╴ $ └─╴ $
// 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()
}
- Output:
┐ ├─╴ banana$ ├─┐ a │ ├─┐ na │ │ ├─╴ na$ │ │ └─╴ $ │ └─╴ $ ├─┐ na │ ├─╴ na$ │ └─╴ $ └─╴ $
#!/usr/bin/env lua
-- Node class implementation
local function Node_new()
return {
sub = "",
ch = {}
}
end
-- Forward declaration
local SuffixTree_addSuffix
-- SuffixTree addSuffix implementation
SuffixTree_addSuffix = function(self, suf)
local nodes = self.nodes
local n = 1 -- Lua arrays are 1-indexed
local i = 1
local suf_len = string.len(suf)
while i <= suf_len do
local b = string.sub(suf, i, i)
local current_node = nodes[n]
local children = current_node.ch
local x2 = 0
local n2 = -1
-- Find matching child
local found = false
for idx, child_idx in ipairs(children) do
local child_node = nodes[child_idx]
local child_sub = child_node.sub
if string.sub(child_sub, 1, 1) == b then
n2 = child_idx
x2 = idx
found = true
break
end
end
if not found then
-- No matching child, remainder of suf becomes new node
n2 = #nodes + 1
local temp = Node_new()
temp.sub = string.sub(suf, i)
table.insert(nodes, temp)
-- Update parent's children list
local parent_node = nodes[n]
table.insert(parent_node.ch, n2)
return self
end
-- Find prefix of remaining suffix in common with child
local child_node = nodes[n2]
local sub2 = child_node.sub
local j = 1
local sub2_len = string.len(sub2)
while j <= sub2_len do
if i + j - 1 > suf_len or string.sub(suf, i + j - 1, i + j - 1) ~= string.sub(sub2, j, j) then
-- Split n2
local n3 = n2
-- New node for the part in common
n2 = #nodes + 1
local temp = Node_new()
temp.sub = string.sub(sub2, 1, j - 1)
temp.ch = {n3}
table.insert(nodes, temp)
-- Old node loses the part in common
local old_node = nodes[n3]
old_node.sub = string.sub(sub2, j)
-- Update parent's child reference
local parent_node = nodes[n]
parent_node.ch[x2] = n2
break
end
j = j + 1
end
i = i + j - 1 -- advance past part in common
n = n2 -- continue down the tree
end
return self
end
-- SuffixTree constructor
local function SuffixTree_new(str)
local self = {
nodes = {}
}
-- Add root node
table.insert(self.nodes, Node_new())
-- Add all suffixes
local len = string.len(str)
for i = 1, len do
local suffix = string.sub(str, i)
self = SuffixTree_addSuffix(self, suffix)
end
return self
end
local function SuffixTree_visualize_f(self, n, pre)
local nodes = self.nodes
local current_node = nodes[n]
local children = current_node.ch
local node_sub = current_node.sub
if #children == 0 then
print("- " .. node_sub)
return
end
print("┐ " .. node_sub)
local children_count = #children
for i = 1, children_count - 1 do
local c = children[i]
io.write(pre .. "├─")
SuffixTree_visualize_f(self, c, pre .. "│ ")
end
io.write(pre .. "└─")
local last_child = children[children_count]
SuffixTree_visualize_f(self, last_child, pre .. " ")
end
local function SuffixTree_visualize(self)
local nodes = self.nodes
if #nodes == 0 then
print("<empty>")
return
end
SuffixTree_visualize_f(self, 1, "")
end
-- Main execution
local tree = SuffixTree_new("banana$")
SuffixTree_visualize(tree)
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
'https://rosettacode.org/wiki/Suffix_tree
Module Suffix_tree {
Class SuffixTree {
Private:
Nodes=List
' Class definition which return a pointer to object
Class Node {
String sub
ch=list
{
read node.sub, Node.ch
->(Node)
break
}
}
module addSuffix (suf as String) {
long n = 0, i = 0, x2, n2
String b
tmp=list
While i < Len(suf)
b=mid(suf,i+1,1)
x2=0
n2=0
do
children=.Nodes(n).ch
if x2=len(children) Then
n2=len(.Nodes)
.Nodes(n2)=.Node(Mid$(suf, i+1))
children(X2)=n2
break ' Exit module
End if
n2=children(x2)
if left(.Nodes(n2).sub,1)=b Then Exit ' Exit do
x2++
Always
sub2=.Nodes(n2).sub
long j=0
While j<len(sub2)
if mid(suf,i+1+j,1)<>mid(sub2, j+1,1) Then
n3=n2
n2=len(.Nodes)
.Nodes(n2)=.Node(Left(sub2,j), List:=0:=n3)
.Nodes(n3).sub=Mid(sub2, j+1)
.Nodes(n).ch(X2)=n2
Exit
End if
j++
End While
i+=j
n=n2
End While
}
Public:
module visualize {
if len(.Nodes)=0 Then ? "<empty>":Exit
visualize_f(0, "")
sub visualize_f(n as long, pre as string)
Local children=.Nodes(n).ch
if len(children)=0 Then
? "- "+.Nodes(n).sub
Else
? "┐ "+.Nodes(n).sub
Pr each(children, 1 , -2), "├─"
Pr each(children, -1), "└─"
End if
End sub
Sub Pr(ch, pre2 as string)
While ch
? pre + pre2;
visualize_f(Eval(ch), pre + "│ ")
End While
End Sub
}
Class:
module SuffixTree (Str as String) {
if len(Str)=0 Then Error "need one character...at least"
.Nodes(0)=.Node()
for i=1 to len(Str)
.addSuffix Mid(Str, i)
next
}
}
M=SuffixTree("banana$")
M.visualize
}
Suffix_tree
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
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()
- Output:
┐ ├─╴banana$ ├─┐a │ ├─┐na │ │ ├─╴na$ │ │ └─╴$ │ └─╴$ ├─┐na │ ├─╴na$ │ └─╴$ └─╴$
Version 1
use strict;
use warnings;
use Data::Dumper;
sub classify {
my $h = {};
for (@_) { push @{$h->{substr($_,0,1)}}, $_ }
return $h;
}
sub suffixes {
my $str = shift;
map { substr $str, $_ } 0 .. length($str) - 1;
}
sub suffix_tree {
return +{} if @_ == 0;
return +{ $_[0] => +{} } if @_ == 1;
my $h = {};
my $classif = classify @_;
for my $key (keys %$classif) {
my $subtree = suffix_tree(
map { substr $_, 1 } @{$classif->{$key}}
);
my @subkeys = keys %$subtree;
if (@subkeys == 1) {
my ($subkey) = @subkeys;
$h->{"$key$subkey"} = $subtree->{$subkey};
} else { $h->{$key} = $subtree }
}
return $h;
}
print +Dumper suffix_tree suffixes 'banana$';
- Output:
$VAR1 = {
'$' => {},
'a' => {
'$' => {},
'na' => {
'na$' => {},
'$' => {}
}
},
'banana$' => {},
'na' => {
'na$' => {},
'$' => {}
}
};
Version 2
#!/usr/bin/perl
use strict;
use warnings;
package Node;
sub new {
my $class = shift;
my $self = {
sub => "", # a substring of the input string
ch => [] # list of child nodes
};
bless $self, $class;
return $self;
}
package SuffixTree;
sub new {
my ($class, $str) = @_;
my $self = {
nodes => []
};
bless $self, $class;
# Add root node
push @{$self->{nodes}}, Node->new();
# Add all suffixes
for my $i (0 .. length($str) - 1) {
$self->addSuffix(substr($str, $i));
}
return $self;
}
sub addSuffix {
my ($self, $suf) = @_;
my $n = 0;
my $i = 0;
while ($i < length($suf)) {
my $b = substr($suf, $i, 1);
my $children = $self->{nodes}->[$n]->{ch};
my $x2 = 0;
my $n2;
while (1) {
if ($x2 == @$children) {
# no matching child, remainder of suf becomes new node
$n2 = @{$self->{nodes}};
my $temp = Node->new();
$temp->{sub} = substr($suf, $i);
push @{$self->{nodes}}, $temp;
push @$children, $n2;
return;
}
$n2 = $children->[$x2];
if (substr($self->{nodes}->[$n2]->{sub}, 0, 1) eq $b) {
last;
}
$x2++;
}
# find prefix of remaining suffix in common with child
my $sub2 = $self->{nodes}->[$n2]->{sub};
my $j = 0;
while ($j < length($sub2)) {
if (substr($suf, $i + $j, 1) ne substr($sub2, $j, 1)) {
# split n2
my $n3 = $n2;
# new node for the part in common
$n2 = @{$self->{nodes}};
my $temp = Node->new();
$temp->{sub} = substr($sub2, 0, $j);
push @{$temp->{ch}}, $n3;
push @{$self->{nodes}}, $temp;
$self->{nodes}->[$n3]->{sub} = substr($sub2, $j); # old node loses the part in common
$self->{nodes}->[$n]->{ch}->[$x2] = $n2;
last; # continue down the tree
}
$j++;
}
$i += $j; # advance past part in common
$n = $n2; # continue down the tree
}
}
sub visualize {
my $self = shift;
if (@{$self->{nodes}} == 0) {
print "<empty>\n";
return;
}
$self->visualize_f(0, "");
}
sub visualize_f {
my ($self, $n, $pre) = @_;
my $children = $self->{nodes}->[$n]->{ch};
if (@$children == 0) {
print "- " . $self->{nodes}->[$n]->{sub} . "\n";
return;
}
print "┐ " . $self->{nodes}->[$n]->{sub} . "\n";
for my $i (0 .. @$children - 2) {
my $c = $children->[$i];
print $pre . "├─";
$self->visualize_f($c, $pre . "│ ");
}
print $pre . "└─";
$self->visualize_f($children->[@$children - 1], $pre . " ");
}
# Main execution
package main;
my $tree = SuffixTree->new("banana\$");
$tree->visualize();
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
with javascript_semantics -- 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] = deep_copy(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) sequence children = deep_copy(t[n][CHILDREN]) children[x2] = n2 t[n][CHILDREN] = children 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)
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $
class Node:
def __init__(self, sub = "", children = None):
self.sub = sub
self.ch = children or []
class SuffixTree:
def __init__(self, str):
self.nodes = [Node()]
for i in range(len(str)):
self.addSuffix(str[i:])
def addSuffix(self, suf):
n, i = 0, 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 += 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 += 1
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, "+-", end = " ")
f(c, pre + " | ")
print(pre, "+-", end = " ")
f(children[-1], pre + " ")
f(0, "")
SuffixTree("banana$").visualize()
- Output:
+- +- -- banana$ +- +- a | +- +- na | | +- -- na$ | | +- -- $ | +- -- $ +- +- na | +- -- na$ | +- -- $ +- -- $
See Suffix trees with Ukkonen’s algorithm by Danny Yoo for more information on how to use suffix trees in Racket.
#lang racket
(require (planet dyoo/suffixtree))
(define tree (make-tree))
(tree-add! tree (string->label "banana$"))
(define (show-node nd dpth)
(define children (node-children nd))
(printf "~a~a ~a~%" (match dpth
[(regexp #px"(.*) $" (list _ d)) (string-append d "`")]
[else else]) (if (null? children) "--" "-+") (label->string (node-up-label nd)))
(let l ((children children))
(match children
((list) (void))
((list c) (show-node c (string-append dpth " ")))
((list c ct ...) (show-node c (string-append dpth " |")) (l ct)))))
(show-node (tree-root tree) "")
- Output:
-+ |-- $ |-+ a | |-- $ | `-+ na | |-- $ | `-- na$ |-+ na | |-- $ | `-- na$ `-- banana$
(formerly Perl 6)
Here is quite a naive algorithm, probably .
The display code is a variant of the visualize a tree task code.
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);
}
- Output:
root ├─$ ├─a │ ├─$ │ └─na │ ├─$ │ └─na$ ├─banana$ └─na ├─$ └─na$
#[derive(Debug, Clone)]
struct Node {
sub: String, // a substring of the input string
ch: Vec<usize>, // vector of child node indices
}
impl Node {
fn new() -> Self {
Node {
sub: String::new(),
ch: Vec::new(),
}
}
fn with_data(sub: String, children: Vec<usize>) -> Self {
Node { sub, ch: children }
}
}
struct SuffixTree {
nodes: Vec<Node>,
}
impl SuffixTree {
fn new(s: &str) -> Self {
let mut tree = SuffixTree {
nodes: vec![Node::new()],
};
for i in 0..s.len() {
tree.add_suffix(&s[i..]);
}
tree
}
fn visualize(&self) {
if self.nodes.is_empty() {
println!("<empty>");
return;
}
self.visualize_node(0, "");
}
fn visualize_node(&self, n: usize, pre: &str) {
let children = &self.nodes[n].ch;
if children.is_empty() {
println!("- {}", self.nodes[n].sub);
return;
}
println!("+ {}", self.nodes[n].sub);
for (i, &child) in children.iter().enumerate() {
if i == children.len() - 1 {
// Last child
print!("{}+-", pre);
self.visualize_node(child, &format!("{} ", pre));
} else {
print!("{}+-", pre);
self.visualize_node(child, &format!("{}| ", pre));
}
}
}
fn add_suffix(&mut self, suf: &str) {
let mut n = 0;
let mut i = 0;
let suf_bytes = suf.as_bytes();
while i < suf.len() {
let b = suf_bytes[i];
let mut x2 = 0;
let n2;
loop {
let children = self.nodes[n].ch.clone();
if x2 == children.len() {
// no matching child, remainder of suf becomes new node
n2 = self.nodes.len();
self.nodes.push(Node::with_data(suf[i..].to_string(), Vec::new()));
self.nodes[n].ch.push(n2);
return;
}
let child_idx = children[x2];
if self.nodes[child_idx].sub.as_bytes()[0] == b {
n2 = child_idx;
break;
}
x2 += 1;
}
// find prefix of remaining suffix in common with child
let sub2 = self.nodes[n2].sub.clone();
let sub2_bytes = sub2.as_bytes();
let mut j = 0;
while j < sub2.len() && i + j < suf.len() {
if suf_bytes[i + j] != sub2_bytes[j] {
// split n2
let n3 = n2;
// new node for the part in common
let new_n2 = self.nodes.len();
let common_part = sub2[..j].to_string();
self.nodes.push(Node::with_data(common_part, vec![n3]));
// old node loses the part in common
self.nodes[n3].sub = sub2[j..].to_string();
self.nodes[n].ch[x2] = new_n2;
break; // continue down the tree
}
j += 1;
}
i += j; // advance past part in common
n = if j < sub2.len() {
// We split the node, use the new intermediate node
self.nodes.len() - 1
} else {
n2
}; // continue down the tree
}
}
}
fn main() {
let tree = SuffixTree::new("banana$");
tree.visualize();
}
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $
func suffix_tree(Str t) {
suffix_tree(^t.len -> map { t.substr(_) })
}
func suffix_tree(a {.len == 1}) {
Hash(a[0] => nil)
}
func suffix_tree(Arr a) {
var h = Hash()
for k,v in (a.group_by { .char(0) }) {
var subtree = suffix_tree(v.map { .substr(1) })
var subkeys = subtree.keys
if (subkeys.len == 1) {
var subk = subkeys[0]
h{k + subk} = subtree{subk}
}
else {
h{k} = subtree
}
}
return h
}
say suffix_tree('banana$')
- Output:
Hash(
"$" => nil,
"a" => Hash(
"$" => nil,
"na" => Hash(
"$" => nil,
"na$" => nil
)
),
"banana$" => nil,
"na" => Hash(
"$" => nil,
"na$" => nil
)
)
import Foundation
class SuffixTreeProblem {
private class Node {
var sub = "" // a substring of the input string
var ch = [Int]() // list of child nodes
}
private class SuffixTree {
private var nodes = [Node]()
init(_ str: String) {
nodes.append(Node())
for i in 0..<str.count {
let startIndex = str.index(str.startIndex, offsetBy: i)
let suffix = String(str[startIndex...])
addSuffix(suffix)
}
}
private func addSuffix(_ suf: String) {
var n = 0
var i = 0
while i < suf.count {
let bIndex = suf.index(suf.startIndex, offsetBy: i)
let b = suf[bIndex]
let children = nodes[n].ch
var x2 = 0
var n2 = 0 // Initialize n2 with a default value
while true {
if x2 == children.count {
// no matching child, remainder of suf becomes new node.
n2 = nodes.count
let temp = Node()
let startIndex = suf.index(suf.startIndex, offsetBy: i)
temp.sub = String(suf[startIndex...])
nodes.append(temp)
nodes[n].ch.append(n2)
return
}
n2 = children[x2]
let firstCharIndex = nodes[n2].sub.startIndex
if nodes[n2].sub[firstCharIndex] == b {
break
}
x2 += 1
}
// find prefix of remaining suffix in common with child
let sub2 = nodes[n2].sub
var j = 0
while j < sub2.count {
let sufIndex = suf.index(suf.startIndex, offsetBy: i + j)
let sub2Index = sub2.index(sub2.startIndex, offsetBy: j)
if suf[sufIndex] != sub2[sub2Index] {
// split n2
let n3 = n2
// new node for the part in common
n2 = nodes.count
let temp = Node()
let endIndex = sub2.index(sub2.startIndex, offsetBy: j)
temp.sub = String(sub2[sub2.startIndex..<endIndex])
temp.ch.append(n3)
nodes.append(temp)
// old node loses the part in common
nodes[n3].sub = String(sub2[endIndex...])
nodes[n].ch[x2] = n2
break // continue down the tree
}
j += 1
}
i += j // advance past part in common
n = n2 // continue down the tree
}
}
func visualize() {
if nodes.isEmpty {
print("<empty>")
return
}
visualize_f(0, "")
}
private func visualize_f(_ n: Int, _ pre: String) {
let children = nodes[n].ch
if children.isEmpty {
print("- \(nodes[n].sub)")
return
}
print("┐ \(nodes[n].sub)")
for i in 0..<children.count - 1 {
let c = children[i]
print("\(pre)├─", terminator: "")
visualize_f(c, pre + "│ ")
}
print("\(pre)└─", terminator: "")
visualize_f(children[children.count - 1], pre + " ")
}
}
static func main() {
SuffixTree("banana$").visualize()
}
}
// Call the main function to run the program
SuffixTreeProblem.main()
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
#!/usr/bin/tclsh
# Node class implementation
proc Node_new {} {
return [dict create sub "" ch [list]]
}
# SuffixTree class implementation
proc SuffixTree_new {str} {
set self [dict create nodes [list]]
# Add root node
dict lappend self nodes [Node_new]
# Add all suffixes
set len [string length $str]
for {set i 0} {$i < $len} {incr i} {
set suffix [string range $str $i end]
set self [SuffixTree_addSuffix $self $suffix]
}
return $self
}
proc SuffixTree_addSuffix {self suf} {
set nodes [dict get $self nodes]
set n 0
set i 0
set suf_len [string length $suf]
while {$i < $suf_len} {
set b [string index $suf $i]
set current_node [lindex $nodes $n]
set children [dict get $current_node ch]
set x2 0
set n2 -1
# Find matching child
set found 0
foreach child_idx $children {
set child_node [lindex $nodes $child_idx]
set child_sub [dict get $child_node sub]
if {[string index $child_sub 0] eq $b} {
set n2 $child_idx
set found 1
break
}
incr x2
}
if {!$found} {
# No matching child, remainder of suf becomes new node
set n2 [llength $nodes]
set temp [Node_new]
dict set temp sub [string range $suf $i end]
lappend nodes $temp
# Update parent's children list
set parent_node [lindex $nodes $n]
set parent_children [dict get $parent_node ch]
lappend parent_children $n2
dict set parent_node ch $parent_children
lset nodes $n $parent_node
dict set self nodes $nodes
return $self
}
# Find prefix of remaining suffix in common with child
set child_node [lindex $nodes $n2]
set sub2 [dict get $child_node sub]
set j 0
set sub2_len [string length $sub2]
while {$j < $sub2_len} {
if {[string index $suf [expr {$i + $j}]] ne [string index $sub2 $j]} {
# Split n2
set n3 $n2
# New node for the part in common
set n2 [llength $nodes]
set temp [Node_new]
dict set temp sub [string range $sub2 0 [expr {$j - 1}]]
dict set temp ch [list $n3]
lappend nodes $temp
# Old node loses the part in common
set old_node [lindex $nodes $n3]
dict set old_node sub [string range $sub2 $j end]
lset nodes $n3 $old_node
# Update parent's child reference
set parent_node [lindex $nodes $n]
set parent_children [dict get $parent_node ch]
lset parent_children $x2 $n2
dict set parent_node ch $parent_children
lset nodes $n $parent_node
break
}
incr j
}
incr i $j ;# advance past part in common
set n $n2 ;# continue down the tree
}
dict set self nodes $nodes
return $self
}
proc SuffixTree_visualize {self} {
set nodes [dict get $self nodes]
if {[llength $nodes] == 0} {
puts "<empty>"
return
}
SuffixTree_visualize_f $self 0 ""
}
proc SuffixTree_visualize_f {self n pre} {
set nodes [dict get $self nodes]
set current_node [lindex $nodes $n]
set children [dict get $current_node ch]
set node_sub [dict get $current_node sub]
if {[llength $children] == 0} {
puts "- $node_sub"
return
}
puts "┐ $node_sub"
set children_count [llength $children]
for {set i 0} {$i < [expr {$children_count - 1}]} {incr i} {
set c [lindex $children $i]
puts -nonewline "${pre}├─"
SuffixTree_visualize_f $self $c "${pre}│ "
}
puts -nonewline "${pre}└─"
set last_child [lindex $children end]
SuffixTree_visualize_f $self $last_child "${pre} "
}
# Main execution
set tree [SuffixTree_new "banana\$"]
SuffixTree_visualize $tree
- Output:
┐ ├─- banana$ ├─┐ a │ ├─┐ na │ │ ├─- na$ │ │ └─- $ │ └─- $ ├─┐ na │ ├─- na$ │ └─- $ └─- $
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()
- Output:
┐ ├─╴ banana$ ├─┐ a │ ├─┐ na │ │ ├─╴ na$ │ │ └─╴ $ │ └─╴ $ ├─┐ na │ ├─╴ na$ │ └─╴ $ └─╴ $
const std = @import("std");
const print = std.debug.print;
const ArrayList = std.ArrayList;
const Allocator = std.mem.Allocator;
const Node = struct {
sub: []u8, // substring of the input string
ch: ArrayList(usize), // vector of child node indices
allocator: Allocator,
fn init(allocator: Allocator) Node {
return Node{
.sub = &[_]u8{},
.ch = ArrayList(usize).init(allocator),
.allocator = allocator,
};
}
fn initWithData(allocator: Allocator, sub: []const u8, children: []const usize) !Node {
var node = Node{
.sub = try allocator.dupe(u8, sub),
.ch = ArrayList(usize).init(allocator),
.allocator = allocator,
};
for (children) |child| {
try node.ch.append(child);
}
return node;
}
fn deinit(self: *Node) void {
if (self.sub.len > 0) {
self.allocator.free(self.sub);
}
self.ch.deinit();
}
};
const SuffixTree = struct {
nodes: ArrayList(Node),
allocator: Allocator,
fn init(allocator: Allocator, s: []const u8) !SuffixTree {
var tree = SuffixTree{
.nodes = ArrayList(Node).init(allocator),
.allocator = allocator,
};
try tree.nodes.append(Node.init(allocator));
for (0..s.len) |i| {
try tree.addSuffix(s[i..]);
}
return tree;
}
fn deinit(self: *SuffixTree) void {
for (self.nodes.items) |*node| {
node.deinit();
}
self.nodes.deinit();
}
fn visualize(self: *const SuffixTree) void {
if (self.nodes.items.len == 0) {
print("<empty>\n" , .{});
return;
}
self.visualizeNode(0, "");
}
fn visualizeNode(self: *const SuffixTree, n: usize, pre: []const u8) void {
const children = &self.nodes.items[n].ch;
if (children.items.len == 0) {
print("- {s}\n", .{self.nodes.items[n].sub});
return;
}
print("+ {s}\n", .{self.nodes.items[n].sub});
for (children.items, 0..) |child, i| {
if (i == children.items.len - 1) {
// Last child
print("{s}+-", .{pre});
// Create new prefix for recursion
var new_pre = std.ArrayList(u8).init(self.allocator);
defer new_pre.deinit();
new_pre.appendSlice(pre) catch return;
new_pre.appendSlice(" ") catch return;
self.visualizeNode(child, new_pre.items);
} else {
print("{s}+-", .{pre});
// Create new prefix for recursion
var new_pre = std.ArrayList(u8).init(self.allocator);
defer new_pre.deinit();
new_pre.appendSlice(pre) catch return;
new_pre.appendSlice("| ") catch return;
self.visualizeNode(child, new_pre.items);
}
}
}
fn addSuffix(self: *SuffixTree, suf: []const u8) !void {
var n: usize = 0;
var i: usize = 0;
while (i < suf.len) {
const b = suf[i];
var x2: usize = 0;
var n2: usize = undefined;
while (true) {
const children = &self.nodes.items[n].ch;
if (x2 == children.items.len) {
// no matching child, remainder of suf becomes new node
n2 = self.nodes.items.len;
const new_node = try Node.initWithData(self.allocator, suf[i..], &[_]usize{});
try self.nodes.append(new_node);
try self.nodes.items[n].ch.append(n2);
return;
}
const child_idx = children.items[x2];
if (self.nodes.items[child_idx].sub.len > 0 and self.nodes.items[child_idx].sub[0] == b) {
n2 = child_idx;
break;
}
x2 += 1;
}
// find prefix of remaining suffix in common with child
const sub2 = self.nodes.items[n2].sub;
var j: usize = 0;
while (j < sub2.len and i + j < suf.len) {
if (suf[i + j] != sub2[j]) {
// split n2
const n3 = n2;
// new node for the part in common
const new_n2 = self.nodes.items.len;
const common_part = sub2[0..j];
const new_node = try Node.initWithData(self.allocator, common_part, &[_]usize{n3});
try self.nodes.append(new_node);
// old node loses the part in common
const remaining_part = try self.allocator.dupe(u8, sub2[j..]);
self.allocator.free(self.nodes.items[n3].sub);
self.nodes.items[n3].sub = remaining_part;
self.nodes.items[n].ch.items[x2] = new_n2;
break; // continue down the tree
}
j += 1;
}
i += j; // advance past part in common
n = if (j < sub2.len)
// We split the node, use the new intermediate node
self.nodes.items.len - 1
else
n2; // continue down the tree
}
}
};
pub fn main() !void {
var gpa = std.heap.GeneralPurposeAllocator(.{}){};
defer _ = gpa.deinit();
const allocator = gpa.allocator();
var tree = try SuffixTree.init(allocator, "banana$");
defer tree.deinit();
tree.visualize();
}
- Output:
+ +-- banana$ +-+ a | +-+ na | | +-- na$ | | +-- $ | +-- $ +-+ na | +-- na$ | +-- $ +-- $