Q:

fastest data structure to find the superstring of a string?

I have a huge vocabulary and want to find all words in the vocabulary that contain the given string. that means I want to find all superstring of a given string among whole vocabulary. However Tree data structure is good for contains() query, and there exist some algorithm to find substrings, but I couldn't find any algorithm to solve this.
I want to use this algorithm ( or data structure )  in Java.

A:

You are looking for a suffix tree.
The idea is, given a string, every prefix of some suffix of this string, is a substring of that string (and every substring is a prefix of some suffix).
This means, you can create a suffix tree of the words, where the "leaf" of each suffix points to the original string.
Now, searching for a substring, you need to traverse the tree by following the nodes of the input substring, and then do some kind of tree traversal (like DFS), to find all reachable leaves. Each such leaf will be a suffix of some string, which the query string is a substring of.
This solution is pretty cheap, it is linear in the size of the output and size of query.

