- Part I Introduction and Preliminaries
1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.2 Suffix sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
1.3 Overview of the Book . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1 Definitions and Notations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.1 Alphabets . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.2 Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.1.3 Model of Computation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2 Data Structures for Strings . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.1 Suffix Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.2 LCP Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.3 Lyndon Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
2.2.4 Document Array . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
About the Author:
Felipe Alves Louza, Dr., Prof., Faculdade de Engenharia Elétrica, Universidade Federal de Uberlândia, Uberlândia - MG, Brazil, 38400-902
Simon Gog, Dr., eBay Inc., San Jose - USA
Guilherme Pimentel Telles, Dr., Prof., Instituto de Computação, Universidade Estadual de Campinas, Campinas - SP, Brazil, 13083-852
