When it comes to full-text indexing, we usually think of methods
such as inverted indices that break text on word boundaries,
consequently requiring search terms to be whole words only. Yet
all of us probably have had the experience of searching for not-
quite-words C++, VM/CMS, SQL*Plus, 127.0.0.1, <blink>, and the
like that were skipped by an inverted index, or broken into
less-distinctive pieces. The same goes when you are working with
data such as DNA sequences, where you need to quickly find any
sequence of symbols. In this article, I examine an indexing
method that lets you find any character sequence in the source
text in time only proportional to the sequence length using a
structure that can compress the entire source text and index
into less space than the text alone. This technique is
exceptionally fast at detecting and counting occurrences of any
string in the source text. The fact that you can build a string
match incrementallyadding one character at a time and seeing the
result at each stepgives