WikiGalaxy
Suffix Tree Basics
Introduction
A suffix tree is a compact representation of all the suffixes of a given string. It is a powerful data structure used for various string processing applications, including substring search and pattern matching.
Structure
The suffix tree for a string S of length n is a rooted directed tree with exactly n leaves numbered 1 to n. Each internal node, other than the root, has at least two children.
class SuffixTreeNode {
Map children = new HashMap<>();
int start, end;
SuffixTreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
Building a Suffix Tree
Naive Approach
The naive approach constructs a suffix tree by inserting each suffix of the string one by one into the tree. This method is simple but inefficient for large strings.
public void buildSuffixTree(String text) {
for (int i = 0; i < text.length(); i++) {
insertSuffix(text.substring(i), i);
}
}
private void insertSuffix(String suffix, int index) {
// Implementation details
}
Ukkonen's Algorithm
Efficient Construction
Ukkonen's algorithm is a linear-time algorithm for constructing suffix trees. It incrementally builds the tree by adding one character at a time, maintaining an active point to optimize the insertion process.
class SuffixTree {
private String text;
private SuffixTreeNode root;
public SuffixTree(String text) {
this.text = text;
root = new SuffixTreeNode(-1, -1);
buildTree();
}
private void buildTree() {
// Implementation of Ukkonen's algorithm
}
}
Applications of Suffix Trees
Pattern Matching
Suffix trees allow for fast pattern matching within a text. Once the suffix tree is built, any substring can be searched in linear time relative to its length.
public boolean search(String pattern) {
SuffixTreeNode currentNode = root;
for (char ch : pattern.toCharArray()) {
if (!currentNode.children.containsKey(ch)) {
return false;
}
currentNode = currentNode.children.get(ch);
}
return true;
}
Longest Repeated Substring
Finding Repeated Patterns
Suffix trees can be used to find the longest repeated substring in a text. By traversing the tree, we can identify the deepest internal node, which corresponds to the longest repeated substring.
public String longestRepeatedSubstring() {
// Traverse the tree to find the deepest internal node
// Return the substring corresponding to that node
return "";
}
