  The string-matching field has grown at a such complicated stage that various
issues come into play when studying it: data structure and algorithmic design,
database principles, compression techniques, architectural features, cache and
prefetching policies. The expertise nowadays required to design good string
data structures and algorithms is therefore transversal to many computer
science fields and much more study on the orchestration of known, or novel,
techniques is needed to make progress in this fascinating topic. This survey is
aimed at illustrating the key ideas which should constitute, in our opinion,
the current background of every index designer. We also discuss the positive
features and drawback of known indexing schemes and algorithms, and devote much
attention to detail research issues and open problems both on the theoretical
and the experimental side.
