After they found where they appear in the first column, we know where na appears.
In the string can be actually found, three matches of na.
This is the last two symbol in ana.
Let's now try to match the first symbol in ana, and
we know where to look for this first symbol.
We'll look for them correspondingly in the last columns of these three strings.
And after we found a in these three rows,
then using again the first last property,
we find where these three occurrences of ana
appears in the beginning of our cyclic rotation.
As a result, we found three matches of ana.
Let me specify some details of the algorithm that we just discussed.
We will use two pointers, top and bottom, that specify the range of
positions in the Burrow-Wheelers matrix that we are interested in.
In the beginning, top will go to 0 and bottom equal to 13,
to cover all positions in the text.
In the next iteration, the range of position we are interested in is narrowed
to all position where a appears in the first column.
Then, what do you do afterwards?
We are looking for the next symbol, which is n in ana,
and we are looking for the first occurrence of this symbol in
the last column among positions from top to bottom, among rows from top to bottom.
And likewise, afterwards, we are looking for the last occurrence of the symbol.
As soon as we found the first and last occurrence of this symbol in this case,
and the first last property will tell us where this n and
all n's in between are hiding in the first column.
As a result, the pointers top and bottom equal to 1 and
6 are changing into 9 and 11, they narrow the search.
And then we continue further, and
that's how we find the positions of ana in the text.
The algorithm that I just described translate in the following
BWMatching pseudocode.
And you can see lines in green describe
what we have been doing with these top and bottom pointers.
Note that we are using last to first array and
given a symbol at position index in lastColumn,
LastToFirst index defines the position of the symbol in the first column.
So it's implement first to last property.