So the solution method that I'll talk about

is the so-called suffix multiway trie.

Generalizing the trie for this problem and so

the idea is if you have given string well what were

going to do is work with all the suffix of the string.

So the original string, ACCTA GGCCT,

we leave off the A, then we have CCTA, and so forth.

So if the string is of size N, then we have N strings for all the suffixes.

And we're going to treat those as different strings,

and just insert them into the trie, that's called a suffix trie.

You now notice that's prefix free, none of these is a prefix

of another because they're all different lengths.

It's a prefix for each set, and we have them

all end with a character that isn't found anywhere else in the trie.

So then the idea is that every internal node of this

trie corresponds to some substring of our original string.

So to answer the question, is x a substring of x?

We use the characters of our query to traverse the trie.

So for example, if we're looking for

ACCTA then [COUGH] when we get to a nonvoid external

node that's tells us that that one is in there and

tells us what position it is so we built the trie AC.

Now if we see something that starts with AC, then we look starting

with position 0 and continue our search and this CCTA is there.

If we encounter a void node then so

for example, if CCT is there because

we found that in the internal node.

But something like TGA, we end up at a void node and router there.

If we reach the end of the string then we're fine,

if we hit a void node we're fine, where a node that is not there.

So this is a very simple algorithm to answer this is x a substring of s

question, and a fine application of tries.

And again the number of void nodes and what does it mean to be a random trie and

how long is the search and so forth.

All of these kinds of questions are going to be important and

relevant in practice.

Here's another application of tries.

Tries is a model for an algorithm, so called leader election algorithm.

This is important in distributed systems, so

the idea is you have a group of individuals.

And they would need to elect a leader, and

what they're going to do is each flip a coin.

So it's than distributed, there could be a large number of them,

they'll each flip a coin and we'll count 1s as winners and 0s as losers.

So everybody that gets a one when they flip a coin survives for

the next round and the ones that get zero are gone.