In this example, this work very well but in practice,

if our query patterns happen to be very long,

this may cause very long lookups, why?

Well, if it's seen here,

the cost of lookup is related to the length of the pattern,

the length of the pattern that we are searching.

But if our pattern is very long,

this may mean that the number of lookups that I

have to do on to trie may also be very long.

So, the question then is,

is there a way to reduce that cost?

Can we reduce that cost and can we make them look up faster for long query patterns?

Well, the answer turns out to be yes and the idea is basically

to take this suffix tree data structures into a new representation,

similar but new representation,

where instead of doing the search based on the length of the pattern,

doing it in a different way.

And then, we will basically call this new data structure as suffix array.

So, the idea is very simple, right?

So, let's take the string that we are given as the data string, we are given that.

And let's create our corresponding trie data structure called suffix tree.

Note that, what we can do is we can focus on the leaves of

this trie data structure.

Just focus on the leaves of the data structure and

then represent the leaves of this data structure,

which are nothing about pointers to the origin of data sequence,

into an array, in the order in which they appear.

So, in this case,

the leftmost pointer is six,

the leftmost array element is six.

The rightmost pointers points to position one and the rightmost array entry is one.

The order in which the pointers are laid out on my trie data structure,

on my suffix tree,

correspond to the order in which pointers are laid out on my array data structure.

So, what's the efficiency of this?

Now, then what happen is that basically we had

a data structure where we could actually search,

now we don't have a data structure,

we only have an array.

So, if you are given the sequence

"the" and we want to find it in our data sequence, how can we do that?

Is there even a way to do that?

Because my tree disappeared,

I removed my tree.

Well, what we can do is we can basically do binary search,

right? What's binary search?

Well, binary search, as you will know from your basic data search and algorithms courses,

a efficient way of doing searches on data that is altered in a particular way.

So, in this case, the particular way is at the right,

we have things that starts with an A and at the left,

this is the left or this is the right?

I think it is the left. Okay.

So, as you know,

the binary search is a efficient way to implement searches on sorted data and here

our data is sorted from left to right in alphabetical order.

At the leftmost position,

we have an, subsequence state start with an.

And at the rightmost position,

we have subsequences that starts with a w. So,

here six corresponds to an,