You should probably look at suffix trees. These slides explain a how these suffix trees can be formed, and how do they solve your problem. The basic idea is to preprocess each key for faster lookup later on. Preprocessing gives you a suffix tree, which is basically a very efficient data structure to look for substrings.