Suffix Tree

Implementation	Space	Time
		Access	Lookup	Insertion	Deletion
Sibling lists / unsorted arrays	O(n)	N/A	O(n)	O(1)	O(1)
Bitwise sibling trees	O(n)	N/A	O(log n)	O(1)	O(1)
Hash maps	O(n)	N/A	O(1)	O(1)	O(n)
Balanced search tree	O(n)	N/A	O(log n)	O(log n)	O(log n)
Sorted arrays	O(n)	N/A	O(log n)	O(n)	O(n)
Hash maps + sibling lists	O(n)	N/A	O(1)	O(1)	O(1)

Definition

Short

Suffix Tree is a tree-based data structure that efficiently represents all suffixes of a given string, enabling fast pattern matching and substring search algorithms

Simplified

Imagine you have a giant book, and a Suffix Tree is like a smart index that helps you quickly find any word or phrase in the book without reading it all over again, making searches faster and more efficient

Detailed

Suffix Tree (also called PAT Tree or Position Tree) is a compressed trie containing all the suffixes of the given text as their keys and positions in the text as their values. Suffix trees allow particularly fast implementations of many important string operations.

Trie vs Suffix Tree

• Suffix Tree is a compressed and optimized version of a Trie, specifically designed for efficient storage and retrieval of all suffixes of a given string, making it more suitable for text-related tasks such as pattern matching and substring searches
• Trie is a tree-like data structure that stores a dynamic set of strings and allows efficient prefix searches

Searching Pattern

When searching for a pattern in a text, preprocessing the pattern can significantly improve search time. Various algorithms like KMP, Rabin Karp, Finite Automata, and Boyer Moore focus on preprocessing patterns. However, an alternative approach is to preprocess the text itself using a suffix tree. Suffix trees, built from the text, allow searching any pattern in O(m) time, where m is the pattern length. This method is particularly efficient for fixed or infrequently changing texts.

To search a pattern in a built suffix tree, start from the root and iterate through each character of the pattern. For every character, follow the edge in the suffix tree if it exists. If not, conclude that the pattern doesn't exist in the text. If all characters of the pattern are processed, a path from the root for the pattern characters indicates a successful pattern search.

Compressed Trie

A suffix tree is essentially a compressed trie for all suffixes of a given text. Building a suffix tree involves generating all suffixes and constructing a compressed trie from them. This trie can be further compressed by joining chains of single nodes, creating the final suffix tree.

Practice

Practice

Aspect	Pseudo Code
Build Suffix Tree	build_suffix_tree(): for index in text.length: _add_suffix(index, root)
Add Suffix	add_suffix(suffix): _add_suffix(0, root) _add_suffix(suffix_start, node): if suffix_start == text.length: return current_char = text[suffix_start] if current_char not in node.children: node.children[current_char] = SuffixNode() node.children[current_char].index = suffix_start else: existing_node = node.children[current_char] _add_suffix(suffix_start + 1, existing_node)
Insertion	insert(new_text): text += new_text for index in range(text.length - new_text.length, text.length): _add_suffix(index, root)
Search	search(pattern): current_node = root n = len(pattern) i = 0 while i < n: char = pattern[i] if char in current_node.children: current_node = current_node.children[char] i += 1 else: return False return True
Delete	delete(pattern): if search(pattern): text = text.replace(pattern, "", 1) root = SuffixNode() build_suffix_tree()
Longest Common Substring	longest_common_substring(): result = [0, 0] _longest_common_substring_dfs(root, "", result) return text.substring(result[0], result[1]) _longest_common_substring_dfs(node, current_suffix, result): if not node.children: return for child in node.children.values(): new_suffix = current_suffix + text[child.index] if len(new_suffix) > result[1] - result[0]: result[0] = child.index - len(new_suffix) + 1 result[1] = child.index + 1 _longest_common_substring_dfs(child, new_suffix, result)
Substring Count	substring_count(node=None): if node is None: node = root count = 1 for child in node.children.values(): count += substring_count(child) return count
Pattern Matching	pattern_matching(pattern, node=None): if node is None: node = root for i, char in enumerate(pattern): if char in node.children: node = node.children[char] else: return [] return _get_leaf_indices(node) _get_leaf_indices(node): indices = [] if not node.children: indices.append(node.index) for child in node.children.values(): indices.extend(_get_leaf_indices(child)) return indices
Traverse	traverse(node=None, depth=0): if node is None: node = root print(" " * depth + "Node: " + node.index) for char, child in node.children.items(): print(" " * (depth + 1) + "Edge: " + char) traverse(child, depth + 2)

Solution

package main

type SuffixNode struct {
	children map[rune]*SuffixNode
	index    int
}

type SuffixTree struct {
	root *SuffixNode
	text string
}

func NewSuffixNode() *SuffixNode {
	return &SuffixNode{
		children: make(map[rune]*SuffixNode),
		index:    -1,
	}
}

func NewSuffixTree(text string) *SuffixTree {
	tree := &SuffixTree{
		root: NewSuffixNode(),
		text: text,
	}
	tree.buildSuffixTree()
	return tree
}

func (st *SuffixTree) buildSuffixTree() {
	n := len(st.text)
	for i := 0; i < n; i++ {
		st.addSuffix(i, st.root)
	}
}

func (st *SuffixTree) addSuffix(suffixStart int, node *SuffixNode) {
	if suffixStart == len(st.text) {
		return
	}

	currentChar := rune(st.text[suffixStart])
	if _, ok := node.children[currentChar]; !ok {
		node.children[currentChar] = NewSuffixNode()
		node.children[currentChar].index = suffixStart
	} else {
		existingNode := node.children[currentChar]
		st.addSuffix(suffixStart+1, existingNode)
	}
}

func (st *SuffixTree) Insert(newText string) {
	st.text += newText
	n := len(st.text)
	for i := n - len(newText); i < n; i++ {
		st.addSuffix(i, st.root)
	}
}

func (st *SuffixTree) Search(pattern string) bool {
	currentNode := st.root
	n := len(pattern)
	i := 0

	for i < n {
		char := rune(pattern[i])
		if child, ok := currentNode.children[char]; ok {
			currentNode = child
			i++
		} else {
			return false
		}
	}

	return true
}

func (st *SuffixTree) Delete(pattern string) {
	if st.Search(pattern) {
		st.text = st.text[:len(st.text)-1]
		st.root = NewSuffixNode()
		st.buildSuffixTree()
	}
}

func (st *SuffixTree) LongestCommonSubstring() string {
	result := []int{0, 0}
	st.longestCommonSubstringDFS(st.root, "", &result)
	return st.text[result[0]:result[1]]
}

func (st *SuffixTree) longestCommonSubstringDFS(node *SuffixNode, currentSuffix string, result *[]int) {
	if len(node.children) == 0 {
		return
	}

	for _, child := range node.children {
		newSuffix := currentSuffix + string(st.text[child.index])

		if len(newSuffix) > (*result)[1]-(*result)[0] {
			(*result)[0] = child.index - len(newSuffix) + 1
			(*result)[1] = child.index + 1
		}

		st.longestCommonSubstringDFS(child, newSuffix, result)
	}
}

func (st *SuffixTree) SubstringCount(node *SuffixNode) int {
	if node == nil {
		node = st.root
	}

	count := 1
	for _, child := range node.children {
		count += st.SubstringCount(child)
	}

	return count
}

func (st *SuffixTree) PatternMatching(pattern string, node *SuffixNode) []int {
	if node == nil {
		node = st.root
	}

	for i, char := range pattern {
		if child, ok := node.children[char]; ok {
			node = child
		} else {
			return nil
		}
	}

	return st.getLeafIndices(node)
}

func (st *SuffixTree) getLeafIndices(node *SuffixNode) []int {
	indices := make([]int, 0)
	if len(node.children) == 0 {
		indices = append(indices, node.index)
	}

	for _, child := range node.children {
		indices = append(indices, st.getLeafIndices(child)...)
	}

	return indices
}

func (st *SuffixTree) Traverse(node *SuffixNode, depth int) {
	if node == nil {
		node = st.root
	}
	fmt.Printf("%sNode: %d\n", "  ", node.index)
	for char, child := range node.children {
		fmt.Printf("%sEdge: %c\n", "  ", char)
		st.Traverse(child, depth+2)
	}
}

import java.util.HashMap;
import java.util.Map;

class SuffixNode {

  Map<Character, SuffixNode> children;
  int index;

  public SuffixNode() {
    children = new HashMap<>();
    index = -1;
  }
}

public class SuffixTree {

  private SuffixNode root;
  private String text;

  public SuffixTree(String text) {
    this.root = new SuffixNode();
    this.text = text;
    buildSuffixTree();
  }

  private void buildSuffixTree() {
    int n = text.length();
    for (int i = 0; i < n; i++) {
      addSuffix(i, root);
    }
  }

  private void addSuffix(int suffixStart, SuffixNode node) {
    if (suffixStart == text.length()) {
      return;
    }

    char currentChar = text.charAt(suffixStart);
    if (!node.children.containsKey(currentChar)) {
      node.children.put(currentChar, new SuffixNode());
      node.children.get(currentChar).index = suffixStart;
    } else {
      SuffixNode existingNode = node.children.get(currentChar);
      addSuffix(suffixStart + 1, existingNode);
    }
  }

  public void insert(String newText) {
    text += newText;
    int n = text.length();
    for (int i = n - newText.length(); i < n; i++) {
      addSuffix(i, root);
    }
  }

  public boolean search(String pattern) {
    SuffixNode currentNode = root;
    int n = pattern.length();
    int i = 0;

    while (i < n) {
      char currentChar = pattern.charAt(i);
      if (currentNode.children.containsKey(currentChar)) {
        currentNode = currentNode.children.get(currentChar);
        i++;
      } else {
        return false;
      }
    }

    return true;
  }

  public void delete(String pattern) {
    if (search(pattern)) {
      text = text.replaceFirst(pattern, "");
      root = new SuffixNode();
      buildSuffixTree();
    }
  }

  public String longestCommonSubstring() {
    int[] result = {0, 0};
    longestCommonSubstringDFS(root, "", result);
    return text.substring(result[0], result[1]);
  }

  private void longestCommonSubstringDFS(SuffixNode node, String currentSuffix, int[] result) {
    if (node.children.isEmpty()) {
      return;
    }

    for (SuffixNode child : node.children.values()) {
      String newSuffix = currentSuffix + text.charAt(child.index);

      if (newSuffix.length() > result[1] - result[0]) {
        result[0] = child.index - newSuffix.length() + 1;
        result[1] = child.index + 1;
      }

      longestCommonSubstringDFS(child, newSuffix, result);
    }
  }

  public int substringCount(SuffixNode node) {
    if (node == null) {
      node = root;
    }

    int count = 1;
    for (SuffixNode child : node.children.values()) {
      count += substringCount(child);
    }

    return count;
  }

  public int[] patternMatching(String pattern, SuffixNode node) {
    if (node == null) {
      node = root;
    }

    for (int i = 0; i < pattern.length(); i++) {
      char currentChar = pattern.charAt(i);
      if (node.children.containsKey(currentChar)) {
        node = node.children.get(currentChar);
      } else {
        return new int[0];
      }
    }

    return getLeafIndices(node);
  }

  private int[] getLeafIndices(SuffixNode node) {
    int[] indices = new int[0];
    if (node.children.isEmpty()) {
      indices = new int[]{node.index};
    }

    for (SuffixNode child : node.children.values()) {
      int[] childIndices = getLeafIndices(child);
      int[] combinedIndices = new int[indices.length + childIndices.length];
      System.arraycopy(indices, 0, combinedIndices, 0, indices.length);
      System.arraycopy(childIndices, 0, combinedIndices, indices.length, childIndices.length);
      indices = combinedIndices;
    }

    return indices;
  }

  public void traverse(SuffixNode node, int depth) {
    if (node == null) {
      node = root;
    }
    System.out.printf("%sNode: %d%n", "  ".repeat(depth), node.index);
    for (Map.Entry<Character, SuffixNode> entry : node.children.entrySet()) {
      char charKey = entry.getKey();
      SuffixNode child = entry.getValue();
      System.out.printf("%sEdge: %c%n", "  ".repeat(depth + 1), charKey);
      traverse(child, depth + 2);
    }
  }
}

class SuffixNode {
  constructor() {
    this.children = {};
    this.index = -1;
  }
}

class SuffixTree {
  constructor(text) {
    this.root = new SuffixNode();
    this.text = text;
    this.buildSuffixTree();
  }

  buildSuffixTree() {
    const n = this.text.length;
    for (let i = 0; i < n; i++) {
      this._addSuffix(i, this.root);
    }
  }

  _addSuffix(suffixStart, node) {
    if (suffixStart === this.text.length) {
      return;
    }

    const currentChar = this.text[suffixStart];
    if (!node.children[currentChar]) {
      node.children[currentChar] = new SuffixNode();
      node.children[currentChar].index = suffixStart;
    } else {
      const existingNode = node.children[currentChar];
      this._addSuffix(suffixStart + 1, existingNode);
    }
  }

  insert(newText) {
    this.text += newText;
    const n = this.text.length;
    for (let i = n - newText.length; i < n; i++) {
      this._addSuffix(i, this.root);
    }
  }

  search(pattern) {
    let currentNode = this.root;
    const n = pattern.length;
    let i = 0;

    while (i < n) {
      const char = pattern[i];
      if (currentNode.children[char]) {
        currentNode = currentNode.children[char];
        i++;
      } else {
        return false;
      }
    }

    return true;
  }

  delete(pattern) {
    if (this.search(pattern)) {
      this.text = this.text.replace(pattern, "");
      this.root = new SuffixNode();
      this.buildSuffixTree();
    }
  }

  longestCommonSubstring() {
    const result = [0, 0];
    this._longestCommonSubstringDFS(this.root, "", result);
    return this.text.substring(result[0], result[1]);
  }

  _longestCommonSubstringDFS(node, currentSuffix, result) {
    if (!Object.keys(node.children).length) {
      return;
    }

    for (const child of Object.values(node.children)) {
      const newSuffix = currentSuffix + this.text[child.index];

      if (newSuffix.length > result[1] - result[0]) {
        result[0] = child.index - newSuffix.length + 1;
        result[1] = child.index + 1;
      }

      this._longestCommonSubstringDFS(child, newSuffix, result);
    }
  }

  substringCount(node = null) {
    if (!node) {
      node = this.root;
    }

    let count = 1;
    for (const child of Object.values(node.children)) {
      count += this.substringCount(child);
    }

    return count;
  }

  patternMatching(pattern, node = null) {
    if (!node) {
      node = this.root;
    }

    for (let i = 0; i < pattern.length; i++) {
      const char = pattern[i];
      if (node.children[char]) {
        node = node.children[char];
      } else {
        return [];
      }
    }

    return this._getLeafIndices(node);
  }

  _getLeafIndices(node) {
    let indices = [];
    if (Object.keys(node.children).length === 0) {
      indices.push(node.index);
    }

    for (const child of Object.values(node.children)) {
      indices = indices.concat(this._getLeafIndices(child));
    }

    return indices;
  }

  traverse(node = null, depth = 0) {
    if (!node) {
      node = this.root;
    }
    console.log("  ".repeat(depth) + `Node: ${node.index}`);
    for (const [char, child] of Object.entries(node.children)) {
      console.log("  ".repeat(depth + 1) + `Edge: ${char}`);
      this.traverse(child, depth + 2);
    }
  }
}

class SuffixNode {
    val children = mutableMapOf<Char, SuffixNode>()
    var index = -1
}

class SuffixTree(text: String) {
    var root = SuffixNode()
    var text = text

    init {
        buildSuffixTree()
    }

    private fun buildSuffixTree() {
        val n = text.length
        for (i in 0 until n) {
            addSuffix(i, root)
        }
    }

    private fun addSuffix(suffixStart: Int, node: SuffixNode) {
        if (suffixStart == text.length) {
            return
        }

        val currentChar = text[suffixStart]
        if (!node.children.containsKey(currentChar)) {
            node.children[currentChar] = SuffixNode()
            node.children[currentChar]!!.index = suffixStart
        } else {
            val existingNode = node.children[currentChar]!!
            addSuffix(suffixStart + 1, existingNode)
        }
    }

    fun insert(newText: String) {
        text += newText
        val n = text.length
        for (i in n - newText.length until n) {
            addSuffix(i, root)
        }
    }

    fun search(pattern: String): Boolean {
        var currentNode = root
        var i = 0

        while (i < pattern.length) {
            val char = pattern[i]
            if (currentNode.children.containsKey(char)) {
                currentNode = currentNode.children[char]!!
                i++
            } else {
                return false
            }
        }

        return true
    }

    fun delete(pattern: String) {
        if (search(pattern)) {
            text = text.replaceFirst(pattern, "")
            root = SuffixNode()
            buildSuffixTree()
        }
    }

    fun longestCommonSubstring(): String {
        val result = intArrayOf(0, 0)
        longestCommonSubstringDFS(root, "", result)
        return text.substring(result[0], result[1])
    }

    private fun longestCommonSubstringDFS(node: SuffixNode, currentSuffix: String, result: IntArray) {
        if (node.children.isEmpty()) {
            return
        }

        for ((_, child) in node.children) {
            val newSuffix = currentSuffix + text[child.index]

            if (newSuffix.length > result[1] - result[0]) {
                result[0] = child.index - newSuffix.length + 1
                result[1] = child.index + 1
            }

            longestCommonSubstringDFS(child, newSuffix, result)
        }
    }

    fun substringCount(node: SuffixNode? = null): Int {
        val currentNode = node ?: root
        var count = 1
        for (child in currentNode.children.values) {
            count += substringCount(child)
        }
        return count
    }

    fun patternMatching(pattern: String, node: SuffixNode? = null): List<Int> {
        val currentNode = node ?: root
        var i = 0
        for (char in pattern) {
            if (currentNode.children.containsKey(char)) {
                currentNode = currentNode.children[char]!!
            } else {
                return emptyList()
            }
        }
        return getLeafIndices(currentNode)
    }

    private fun getLeafIndices(node: SuffixNode): List<Int> {
        val indices = mutableListOf<Int>()
        if (node.children.isEmpty()) {
            indices.add(node.index)
        }

        for (child in node.children.values) {
            indices.addAll(getLeafIndices(child))
        }

        return indices
    }

    fun traverse(node: SuffixNode? = null, depth: Int = 0) {
        val currentNode = node ?: root
        println("  ".repeat(depth) + "Node: ${currentNode.index}")
        for ((char, child) in currentNode.children) {
            println("  ".repeat(depth + 1) + "Edge: $char")
            traverse(child, depth + 2)
        }
    }
}

class SuffixTree:
    def __init__(self, text):
        self.root = SuffixNode()
        self.text = text
        self.build_suffix_tree()

    def build_suffix_tree(self):
        n = len(self.text)
        for i in range(n):
            self._add_suffix(i, self.root)

    def _add_suffix(self, suffix_start, node):
        if suffix_start == len(self.text):
            return

        current_char = self.text[suffix_start]
        if current_char not in node.children:
            node.children[current_char] = SuffixNode()
            node.children[current_char].index = suffix_start
        else:
            existing_node = node.children[current_char]
            self._add_suffix(suffix_start + 1, existing_node)

    def insert(self, new_text):
        self.text += new_text
        n = len(self.text)
        for i in range(n - len(new_text), n):
            self._add_suffix(i, self.root)

    def search(self, pattern):
        current_node = self.root
        n = len(pattern)
        i = 0

        while i < n:
            char = pattern[i]
            if char in current_node.children:
                current_node = current_node.children[char]
                i += 1
            else:
                return False

        return True

    def delete(self, pattern):
        if self.search(pattern):
            self.text = self.text.replace(pattern, "", 1)
            self.root = SuffixNode()
            self.build_suffix_tree()

    def longest_common_substring(self):
        result = [0, 0]
        self._longest_common_substring_dfs(self.root, "", result)
        return self.text[result[0]:result[1]]

    def _longest_common_substring_dfs(self, node, current_suffix, result):
        if not node.children:
            return

        for child in node.children.values():
            new_suffix = current_suffix + self.text[child.index]

            if len(new_suffix) > result[1] - result[0]:
                result[0] = child.index - len(new_suffix) + 1
                result[1] = child.index + 1

            self._longest_common_substring_dfs(child, new_suffix, result)

    def substring_count(self, node=None):
        if node is None:
            node = self.root

        count = 1
        for child in node.children.values():
            count += self.substring_count(child)

        return count

    def pattern_matching(self, pattern, node=None):
        if node is None:
            node = self.root

        for i, char in enumerate(pattern):
            if char in node.children:
                node = node.children[char]
            else:
                return []

        return self._get_leaf_indices(node)

    def _get_leaf_indices(self, node):
        indices = []
        if not node.children:
            indices.append(node.index)

        for child in node.children.values():
            indices.extend(self._get_leaf_indices(child))

        return indices

    def traverse(self, node=None, depth=0):
        if node is None:
            node = self.root
        print("  " * depth + f"Node: {node.index}")
        for char, child in node.children.items():
            print("  " * (depth + 1) + f"Edge: {char}")
            self.traverse(child, depth + 2)

use std::collections::HashMap;

struct SuffixNode {
    children: HashMap<char, SuffixNode>,
    index: i32,
}

impl SuffixNode {
    fn new() -> Self {
        SuffixNode {
            children: HashMap::new(),
            index: -1,
        }
    }
}

struct SuffixTree {
    root: SuffixNode,
    text: String,
}

impl SuffixTree {
    fn new(text: &str) -> Self {
        let mut tree = SuffixTree {
            root: SuffixNode::new(),
            text: text.to_string(),
        };
        tree.build_suffix_tree();
        tree
    }

    fn build_suffix_tree(&mut self) {
        let n = self.text.len();
        for i in 0..n {
            self.add_suffix(i, &mut self.root);
        }
    }

    fn add_suffix(&mut self, suffix_start: usize, node: &mut SuffixNode) {
        if suffix_start == self.text.len() {
            return;
        }

        let current_char = self.text.chars().nth(suffix_start).unwrap();
        if !node.children.contains_key(&current_char) {
            node.children.insert(current_char, SuffixNode::new());
            if let Some(child) = node.children.get_mut(&current_char) {
                child.index = suffix_start as i32;
            }
        } else {
            if let Some(existing_node) = node.children.get_mut(&current_char) {
                self.add_suffix(suffix_start + 1, existing_node);
            }
        }
    }

    fn insert(&mut self, new_text: &str) {
        self.text.push_str(new_text);
        let n = self.text.len();
        for i in n - new_text.len()..n {
            self.add_suffix(i, &mut self.root);
        }
    }

    fn search(&self, pattern: &str) -> bool {
        let mut current_node = &self.root;
        let mut i = 0;

        while i < pattern.len() {
            if let Some(char) = pattern.chars().nth(i) {
                if let Some(child) = current_node.children.get(&char) {
                    current_node = child;
                    i += 1;
                } else {
                    return false;
                }
            }
        }

        true
    }

    fn delete(&mut self, pattern: &str) {
        if self.search(pattern) {
            self.text = self.text.replacen(pattern, "", 1);
            self.root = SuffixNode::new();
            self.build_suffix_tree();
        }
    }

    fn longest_common_substring(&self) -> String {
        let mut result = vec![0, 0];
        self.longest_common_substring_dfs(&self.root, "", &mut result);
        self.text[result[0] as usize..result[1] as usize].to_string()
    }

    fn longest_common_substring_dfs(&self, node: &SuffixNode, current_suffix: &str, result: &mut Vec<i32>) {
        if node.children.is_empty() {
            return;
        }

        for (_, child) in &node.children {
            let new_suffix = format!("{}{}", current_suffix, &self.text[child.index as usize..(child.index + 1) as usize]);

            if new_suffix.len() > (result[1] - result[0]) as usize {
                result[0] = child.index - new_suffix.len() as i32 + 1;
                result[1] = child.index + 1;
            }

            self.longest_common_substring_dfs(child, &new_suffix, result);
        }
    }

    fn substring_count(&self, node: Option<&SuffixNode>) -> i32 {
        let current_node = node.unwrap_or(&self.root);
        let mut count = 1;
        for (_, child) in &current_node.children {
            count += self.substring_count(Some(child));
        }
        count
    }

    fn pattern_matching(&self, pattern: &str, node: Option<&SuffixNode>) -> Vec<i32> {
        let mut current_node = node.unwrap_or(&self.root);
        let mut i = 0;

        for char in pattern.chars() {
            if let Some(child) = current_node.children.get(&char) {
                current_node = child;
            } else {
                return Vec::new();
            }
            i += 1;
        }

        self.get_leaf_indices(current_node)
    }

    fn get_leaf_indices(&self, node: &SuffixNode) -> Vec<i32> {
        let mut indices = Vec::new();
        if node.children.is_empty() {
            indices.push(node.index);
        }

        for (_, child) in &node.children {
            indices.extend(self.get_leaf_indices(child));
        }

        indices
    }

    fn traverse(&self, node: Option<&SuffixNode>, depth: i32) {
        let current_node = node.unwrap_or(&self.root);
        println!("{}Node: {}", "  ".repeat(depth as usize), current_node.index);
        for (char, child) in &current_node.children {
            println!("{}Edge: {}", "  ".repeat((depth + 1) as usize), char);
            self.traverse(Some(child), depth + 2);
        }
    }
}

class SuffixNode {
  children: { [char: string]: SuffixNode };
  index: number;

  constructor() {
    this.children = {};
    this.index = -1;
  }
}

class SuffixTree {
  root: SuffixNode;
  text: string;

  constructor(text: string) {
    this.root = new SuffixNode();
    this.text = text;
    this.buildSuffixTree();
  }

  buildSuffixTree(): void {
    const n = this.text.length;
    for (let i = 0; i < n; i++) {
      this.addSuffix(i, this.root);
    }
  }

  insert(newText: string): void {
    this.text += newText;
    const n = this.text.length;
    for (let i = n - newText.length; i < n; i++) {
      this.addSuffix(i, this.root);
    }
  }

  search(pattern: string): boolean {
    let currentNode = this.root;
    let i = 0;

    while (i < pattern.length) {
      const char = pattern[i];
      if (char in currentNode.children) {
        currentNode = currentNode.children[char];
        i++;
      } else {
        return false;
      }
    }

    return true;
  }

  delete(pattern: string): void {
    if (this.search(pattern)) {
      this.text = this.text.replace(pattern, "");
      this.root = new SuffixNode();
      this.buildSuffixTree();
    }
  }

  longestCommonSubstring(): string {
    const result: [number, number] = [0, 0];
    this.longestCommonSubstringDFS(this.root, "", result);
    return this.text.slice(result[0], result[1]);
  }

  substringCount(node?: SuffixNode): number {
    const currentNode = node || this.root;
    let count = 1;

    for (const child of Object.values(currentNode.children)) {
      count += this.substringCount(child);
    }

    return count;
  }

  patternMatching(pattern: string, node?: SuffixNode): number[] {
    const currentNode = node || this.root;
    let i = 0;

    for (const char of pattern) {
      if (char in currentNode.children) {
        currentNode = currentNode.children[char];
      } else {
        return [];
      }
      i++;
    }

    return this.getLeafIndices(currentNode);
  }

  traverse(node?: SuffixNode, depth: number = 0): void {
    const currentNode = node || this.root;
    console.log("  ".repeat(depth) + `Node: ${currentNode.index}`);
    for (const [char, child] of Object.entries(currentNode.children)) {
      console.log("  ".repeat(depth + 1) + `Edge: ${char}`);
      this.traverse(child, depth + 2);
    }
  }

  private addSuffix(suffixStart: number, node: SuffixNode): void {
    if (suffixStart === this.text.length) {
      return;
    }

    const currentChar = this.text[suffixStart];
    if (!(currentChar in node.children)) {
      node.children[currentChar] = new SuffixNode();
      node.children[currentChar].index = suffixStart;
    } else {
      const existingNode = node.children[currentChar];
      this.addSuffix(suffixStart + 1, existingNode);
    }
  }

  private longestCommonSubstringDFS(
    node: SuffixNode,
    currentSuffix: string,
    result: [number, number],
  ): void {
    if (Object.keys(node.children).length === 0) {
      return;
    }

    for (const child of Object.values(node.children)) {
      const newSuffix = currentSuffix + this.text[child.index];

      if (newSuffix.length > result[1] - result[0]) {
        result[0] = child.index - newSuffix.length + 1;
        result[1] = child.index + 1;
      }

      this.longestCommonSubstringDFS(child, newSuffix, result);
    }
  }

  private getLeafIndices(node: SuffixNode): number[] {
    const indices: number[] = [];
    if (Object.keys(node.children).length === 0) {
      indices.push(node.index);
    }

    for (const child of Object.values(node.children)) {
      indices.push(...this.getLeafIndices(child));
    }

    return indices;
  }
}