Game combo press model (substring search)

I'm trying to make a model for checking combo presses in a game. Given a list of Button (enum) presses, it returns the list of possible combos completed. I tried using a suffix tree, but I'm not sure if this is the best solution. It's also my first time writing a suffix tree, and I don't know if this is the correct usage.

Also, could someone help me analyze the runtime of registering combos and searching combos? I think registering combos is O(n), but what about searching for combos?

Button enum:

public enum Button {
        Left, Right, Down, Up, A, B, X, Y;
}

Registering combos and for searching for the completed combos:

```
public class SuffixTree {
private class SuffixTreeNode {
Map children = new HashMap();
List indices = new ArrayList();

public void insert(List lob) {
if (lob != null && lob.size() > 0) {
indices.add(lob.get(0));
Button value = lob.get(0);
SuffixTreeNode child = null;
if (children.containsKey(value)) {
child = children.get(value);
} else {
child = new SuffixTreeNode();
children.put(value, child);
}
List remainder = lob.subList(1, lob.size());
child.insert(remainder);
}
}

public List search(List lob, List parents) {
if (lob == null || lob.isEmpty()) {
return parents;
} else {
Button first = lob.get(0);
if (children.containsKey(first)) {
parents.add(first);
List remainder = lob.subList(1, lob.size());
return children.get(first).search(remainder, parents);
}
}
return null;
}
}

SuffixTreeNode root = new SuffixTreeNode();

public void registerCombos(List> combos) {
for (List combo :

Bug

Since you never mark your suffix tree nodes as end nodes, your search will find combos that don't exist. For example, if ABXY is a registered combo, and you search for AB, it will return both A and AB as combos. You should have a boolean per node telling you whether the node is the end of a combo or not.

Efficiency

You appear to search for all sublists that end with the end of the original list. For example, if the original search list were ABXY,you would search for these sublists: ABXY BXY XY Y.

Given this behavior, you could greatly improve your suffix tree by storing the combos in reverse order. Then, when you want to search for a given list and all of its sublists, you search the suffix tree once in reverse order. For example, given ABXY, you search the suffix tree for YXBA and return up to four combos that match (Y YX YXB YXBA). This would reduce your search from \$O(n^2)\$ to \$O(n)\$.

How to mark end nodes

This is in response to the comment. Given a tree with combos A B X Y ABXY, the tree would look like this:

Root
                      /  |   |  \ 
                     A*  B*  X*  Y*
                    B
                   X
                  Y*

In the tree above, the end nodes are marked with a . So if you searched for combo AB, it would go down the left branch from the root but it would not find a combo because the node B on the left branch does not have a .

Why searching in reverse order is more efficient

Suppose you are given combos A B X Y ABXY. If you reversed each combo and added to a tree, your tree would look like:

Root
                      /  |   |  \ 
                     A*  B*  X*  Y*
                                  X
                                   B
                                    A*

Now suppose you were given ABXY as your search list, meaning you actually want to search for the four sublists ABXY BXY XY Y. You could do this in one search by searching for YXBA and returning a positive match every time you find an end node. So in the tree above, you would follow the rightmost path four levels, passing by the lists Y YX YXB YXBA. Since Y and A are marked as end nodes, you would return Y and YXBA as matches. After reversing, these would correspond to Y and ABXY as matches. Notice that you only have to traverse the tree once instead of 4 times.

StackExchange Code Review Q#138073, answer score: 2