org.sonar.duplications.detector.suffixtree
Class SuffixTree

java.lang.Object
  org.sonar.duplications.detector.suffixtree.SuffixTree

public final class SuffixTree
extends Object

Provides algorithm to construct suffix tree.

Suffix tree for the string S of length n is defined as a tree such that:

• the paths from the root to the leaves have a one-to-one relationship with the suffixes of S,
• edges spell non-empty strings,
• and all internal nodes (except perhaps the root) have at least two children.

Since such a tree does not exist for all strings, S is padded with a terminal symbol not seen in the string (usually denoted $). This ensures that no suffix is a prefix of another, and that there will be n leaf nodes, one for each of the n suffixes of S. Since all internal non-root nodes are branching, there can be at most n − 1 such nodes, and n + (n − 1) + 1 = 2n nodes in total. All internal nodes and leaves have incoming edge, so number of edges equal to number of leaves plus number of inner nodes, thus at most 2n - 1. Construction takes O(n) time.

This implementation was adapted from Java-port of Mark Nelson's C++ implementation of Ukkonen's algorithm.

Method Summary

static SuffixTree	create(Text text)
Node	getRootNode()
Object	symbolAt(int index)

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Method Detail

create

public static SuffixTree create(Text text)

symbolAt

public Object symbolAt(int index)

getRootNode

public Node getRootNode()