Okay. Let's see an example how this data structure can be used to trigger patterns.
Let's see an example, data sequence.
Let's say our example data sequence starts with a d. Continue to c,
then a b, then a,
then b, then c,
then another a, then another b,
then another c, then another a,
d, a and b and dot dot dot dot.
Let's see what will happen. So, at the beginning we see a d,
and we are at the start pole.
d is not an a.
So, it means that basically,
we will basically say at the start position.
The next symbol that we see is a c. It is still not a.
So, we'll stay at the start position.
The next symbol that we see is a b.
That's fine. So, we are not seeing our trigger pattern.
So, we are still at the start position.
The next symbol in the sequence is an a.
This is the first symbol of our trigger pattern.
So, we'll move along this edge and I will arrive to the state a.
At this point we have seen a.
The next sequence is a b. Oh,
looks like there's a chance our trigger pattern maybe matching,
because we've seen not only a but also to b.
The next sequence is a c. C is the next sequence in our pattern.
So, we have not only seen a and b,
but also have seen c. So,
three of the seven event in our sequence have been matched so far.
The next sequence is an a. Oh,
looks like our pattern is indeed evolving,
because from c the next symbol is an a.
So, I arrive to a position.
So, we have seen a, b, c, a.
So, we have seen four of our seven symbol sequence.
The next sequence is a b. What does this mean?
It means that our pattern is not matching yet,
because if our partner was matching,
the next sequence should have been d. But the next sequence in our data is a b.
So, that means that we need to go back.
How how far do we need to get back?
Well, one possible is that we can go all the way back to the start.
However, do we need to go that much back in history?
It turns out that we don't.
Why? Well, it is true that we have seen a b,
but if you look at here,
at this point we have not just seen b,
but we have really seen an a, b.
An a, b is the first two sequences on our target pattern.
Which means that from this position,
instead of jumping all the way to the start,
we need to jump only to this position.
This should've been a b. I apologize.
This should also have been b. I apologize for that.
So, from a I jump back to the state that I have seen ab.
This essentially saved us having to revisit this a and this b again.
So, this is actually where the savings of the Knuth-Morris-Pratt data actual comes.
Let's see what happens next.
We have seen a c, c took us to the states c again.
Dummy c and a, that takes us to the state a,
then we see a d. Well,
that takes us to the next state d. We see an a.
That takes us to the state where we have seen a,
and at that point we see a b and b takes us to our trigger state.
Essentially what happened is that using our finite set automata,
we have triggered our target pattern at this position.
The saving that happened in this data structures for the sequence is here.
So, instead of jumping to the very beginning is a failure.
By jumping to this point,
I essentially saved lookups,
two lookups at this point position.
By doing this two look-up savings,
essentially what I can guarantee is that
the search can be done in a linear time of the data structure.
What about if we are not given a single pattern but we are given multiple patterns.
Can we also have savings across multiple patterns?
Now we know that basically using KMP data structure,
we can leverage redundancies within a single query pattern.
But what about if you are them multiple patterns,
can we also leverage redundancies across multiple patterns to reduce the search time?
It turns out that we can actually do that and
the Aho-Corasick Trie is a data structure that actually enables us to achieve this.
So let's see how the Aho-Corasick Trie works.
In this case, let's say that we are given a query pattern ABCDAB,
and the query pattern CADD,