Figure 3(c): Extending "br" to "abr." The next char is "a," so you start with the range of F containing as. Narrow this range down from all a's to a's followed by "br," again by inverting FL from the "br" range into the "a" range. This process can continue indefinitely, left-extending the pattern one character at each step. For any pattern, this process will give you the start and end (and count) of a range of matches in M. From any position in this range, you can decode forward to show the context of each match, but you don't know the offset of each match in the source file.

Back to Article