/**

* An abstract class for Suffix Trees.

*

* @author Paul Chew for CS409, Apr 2000.

*

* A Suffix Tree is built from a single string and contains all suffixes of

* that string. For this implementation, only letters and the separator ($)

* can appear in the string.

*

* The separators ($s) are treated specially: they terminate suffixes.

* In other words, each suffix is stored only up to its first $. This implies

* that identical suffixes can be stored in the tree. To handle this situation

* this implementation allows multiple leaf nodes.

*/

public abstract class SuffixTree {

/* Internal classes */

/**

* Generic tree node. Parent class of LeafNode and InternalNode.

*/

class Node { // Generic tree node

}

/**

* Leaf node. Holds a suffix ID (where the suffix begins in the string).

* For this implementation, a suffix can appear multiple times in the

* same tree; this is because $ is treated as a separator/terminator.

* The more field allows a linked list of leaf nodes. Using this,

* multiple suffixes can be stored at one "leaf".

*/

class LeafNode extends Node { // Leaf node

int beginIndex; // ID for the suffix that ends here

LeafNode more; // More than one suffix can end here

}

/**

* Internal node. Each internal node has up to 27 children, one for

* each letter and one for the separator ($). Letters are stored in

* locations 1 through 26 and the separator corresponds to location 0.

*/

class InternalNode extends Node { // Internal (nonleaf) node

Edge[] child = new Edge[27]; // Child for each letter + separator

}

/**

* Tree edge. Each edge corresponds to a substring of the original string.

* The beginIndex and endIndex define this substring. The node is the

* node (either LeafNode or InternalNode) that this edge goes to. The

* inclusive/exclusive rules used on the indices are chosen to match

* the arguments to String.substring().

*/

class Edge { // Tree edge (labeled with a substring)

int beginIndex; // Beginning index, inclusive

int endIndex; // Ending index, exclusive

Node node; // Child node

}

/* Fields */

/**

* The Suffix Tree.

* The root is the root of the entire suffix tree.

* The string is the original string (after converting to lower case

* and appending of a $ if necessary). Indices stored within the suffix

* tree refer to locations within the string.

*/

InternalNode root = null; // Root of the SuffixTree

String string; // String that is held in SuffixTree

/* Abstract Methods */

/**

* Constructor; create a SuffixTree.

* The input string should consist only of letters and the separator ($).

* If the original string does not end with '$' then '$' is appended.

*/

public SuffixTree (String inputString) {

// This does nothing.

// You have to implement a constructor that actually does

// something for MySuffixTree.

}

/**

* Constructor; create a SuffixTree.

* This version is needed here just so that the constructor in

* MySuffixTree will work properly. This constructor is called automatically

* by the system as the first step of the MySuffixTree constructor.

* Your constructor for MySuffixTree should look like the previous

* constructor (i.e., it should take a string as input) rather than

* this constructor.

*/

public SuffixTree () {}

/**

* Find all occurrences of a query string.

* @return an array of integer indices showing all the places in

* the original string where the query string starts; note that

* the size of the array matches the number of occurrences

*/

public abstract int[] findAll (String query);

/**

* Locate the longest prefix of the given query string that appears as a

* suffix in the SuffixTree.

* @param query the query string

* @return an array of integer indices showing all the places in

* the original string where the longest prefix starts

*/

public abstract int[] longestPrefix (String query);

/* Other Methods */

/**

* Shows all suffixes stored in the tree in sorted (alphabetical) order.

* If the SuffixTree is built correctly this is easy to do recursively.

* @return a String representation of the SuffixTree.

*/

public String toString () {

// Note: "\n" is treated as end-of-line when used within a String.

return "SuffixTree for " + string + ":" + toString("\n ",root);

}

/**

* Shows all Strings stored in the give subtree. Each string has

* prefix placed in front of it. This implementation is not

* particularly efficient; it does a lot of String recopying.

* @param prefix a prefix string

* @param node the subtree

* @return a String representation of the subtree

*/

private String toString(String prefix, InternalNode node) {

StringBuffer buf = new StringBuffer();

// Create strings for each edge leaving this node.

for (int i = 0; i < node.child.length; i++) {

Edge e = node.child[i];

if (e == null) continue; // Skip unused edges

// String for this edge; include '.' as node marker.

String edgeString = "." + string.substring(e.beginIndex,e.endIndex);

// If we are at a leaf node, we create the string.

if (e.node instanceof LeafNode) {

LeafNode leaf = (LeafNode)e.node;

// Include the edge string and the ID of corresponding suffix.

buf.append(prefix + edgeString + " " + leaf.beginIndex);

// Include suffix data from any extra leaf nodes.

while (leaf.more != null) {

leaf = leaf.more;

buf.append("," + leaf.beginIndex);

}

}

// If not at a leaf node, we recursively build the strings

// corresponding to this node. The prefix changes.

else buf.append(toString(prefix+edgeString,(InternalNode)e.node));

}

return buf.toString();

}

/**

* Return a string representation of an array of integers. Used for

* printing results of subtree searches.

* @param array the array of integers

* @return a String representation of the array of integers

*/

static String toString (int[] array) {

if (array.length == 0) return "{}";

StringBuffer buf = new StringBuffer("{" + array[0]);

for (int i = 1; i < array.length; i++)

buf.append("," + array[i]);

return buf.append("}").toString();

}

/**

* A simple testing program for suffix trees.

* @param string the string used to build the suffix tree

*/

private static void test (String string) {

SuffixTree tree;

tree = new MySuffixTree(string);

System.out.println(tree);

System.out.println("'miss' occurs at " + toString(tree.findAll("miss")));

System.out.println("'is' occurs at " + toString(tree.findAll("is")));

System.out.println("'i' occurs at " + toString(tree.findAll("i")));

System.out.println("The longest prefix of 'issue' occurs at " +

toString(tree.longestPrefix("issue")));

System.out.println();

}

/* Main Program */

/**

* Main program; used for testing.

*/

public static void main (String[] args) {

test("mississippi$");

test("mississippi$missouri$");

test("indiana$louisiana$");

test("data$structures$and$algorithms$sure$are$fun$");

}

}