**TL;DR** 

Is there a data structure that'd quickly let me match words at any point (e.g., 'foo' matches 'foobar' and 'zoofoo'), and, ideally, returns a list of "characters that show up after the needle" (e.g., 'foo' should return ['b', $]).

---

I'm implementing an algorithm that generates random words from a training set of other words.

In simple terms, it's basically like this:

1. Choose an arbitrary starting point.
2. Choose the longest suffix of the current word that is contained in at least 2 other words
3. Choose one of those words at random, and append the next character to the current wor.
4. GOTO 2 until "next character" is EOW

e.g., if the current word is 'tat', some valid options would be 'potato' and 'tattoo'; if the current word is "ophtalmi", the only option is "ophtalmic", so we search if any words contain "phtalmi", "htalmi", "talmi", and so on.

I've tried a couple of implementations: in one, I've used a trie populated with every suffix of every word. This is very fast at generating words, but populating the trie is VERY slow (~4 million words have not finished in over 10 hours).

In another, I've generated a hash of:

```
for word in words:
    for suffix in tails(words):
        for prefix, suffix in prefixes(words): # prefixes("foo") = [("f","oo"),("fo","o"),("foo","")]
            ngrams[prefix].add(suffix) # this is a set

```

and it's much faster at reading the training set, and very fast at generating, but it takes a lot of RAM.

And, finally, the dumb option, of simply searching

```
candidates = [word for word in words if string in words]

```

which takes very little memory, but is much slower.

Is there a data structure with the behaviour I need?