Contents

1 Introduction 5 1.1 Texts and their processing . . . . . . . . . . . . . . . . . . . 5 1.2 Text file facilities . . . . . . . . . . . . . . . . . . . . . . . . 5 1.3 Dictionaries . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Data compression . . . . . . . . . . . . . . . . . . . . . . . . 5 1.5 Applications of text algorithms in genetics . . . . . . . . . . 5 1.6 Structure of the book . . . . . . . . . . . . . . . . . . . . . 5

2 Foundations 7 2.1 Machine models and presentation of algorithms . . . . . . . 7 2.2 Efficiency of algorithms . . . . . . . . . . . . . . . . . . . . 7 2.3 Notation and formal definitions of basic problems on texts . 7 2.4 Combinatorics of texts . . . . . . . . . . . . . . . . . . . . . 7

3 Basic string-matching algorithms 9 3.1 The Knuth-Morris-Pratt algorithm . . . . . . . . . . . . . . 9 3.2 The Simon algorithm . . . . . . . . . . . . . . . . . . . . . . 9 3.3 String matching by duels . . . . . . . . . . . . . . . . . . . 9 3.4 String matching by sampling . . . . . . . . . . . . . . . . . 9

4 The Boyer-Moore algorithm and its variations 11 4.1 The Boyer-Moore algorithm . . . . . . . . . . . . . . . . . . 11 4.2 * Analysis of Boyer-Moore algorithm . . . . . . . . . . . . . 11 4.3 Galil’s improvement . . . . . . . . . . . . . . . . . . . . . . 11 4.4 The Turbo BM algorithm . . . . . . . . . . . . . . . . . . . 11 4.5 * Analysis of Turbo BM algorithm . . . . . . . . . . . . . . 11 4.6 Other variations of Boyer-Moore algorithm . . . . . . . . . 11 5 Suffix trees 13

5.1 Prelude to McCreight and Weiner algorithms . . . . . . . . 13 5.2 Two compressed versions of the naive representation …. 13 5.3 McCreight’s algorithm . . . . . . . . . . . . . . . . . . . . . 13 5.4 Weiner’s algorithm . . . . . . . . . . . . . . . . . . . . . . . 13 5.5 Ukkonen’s algorithm . . . . . . . . . . . . . . . . . . . . . . 13 5.6 Suffix arrays: an alternative data structure . . . . . . . . . 13 5.7 Applications . . . . . . . . . . . . . . . . . . . . . . . . . . . 13

6 Subword graphs 15 6.1 Size of suffix DAWGs . . . . . . . . . . . . . . . . . . . . . . 15 6.2 A simple off-line construction . . . . . . . . . . . . . . . . . 15 6.3 On-line construction . . . . . . . . . . . . . . . . . . . . . . 15 6.4 * Further relations between suffix trees and suffix dawgs . . 15 6.5 String-matching using suffix dawg’s . . . . . . . . . . . . . . 15

7 Automata theoretic approach 17 7.1 Aho-Corasick automaton . . . . . . . . . . . . . . . . . . . . 17 7.2 Faster multi-pattern matching . . . . . . . . . . . . . . . . . 17 7.3 Regular expression matching . . . . . . . . . . . . . . . . . 17 7.4 * Determinization of finite automata: efficient instances . . 17 7.5 * Two-way pushdown automata . . . . . . . . . . . . . . . . 17

8 Regularities in texts: symmetries and repetitions 19 8.1 KMR algorithm: longest repeated factors in words and arrays 19 8.2 Finding squares . . . . . . . . . . . . . . . . . . . . . . . . . 19 8.3 Symmetries in texts . . . . . . . . . . . . . . . . . . . . . . 19

9 Almost optimal parallel algorithms 21 9.1 Building the dictionary of basic factors in parallel . . . . . . 21 9.2 Parallel construction of string-matching automata . . . . . 21 9.3 Parallel computation of regularities . . . . . . . . . . . . . . 21 9.4 Parallel computation of suffix trees . . . . . . . . . . . . . . 21 9.5 * Parallel computation of dawgs . . . . . . . . . . . . . . . 21

10 Text compression techniques 23 10.1 Substitutions . . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.2 Static Huffman coding . . . . . . . . . . . . . . . . . . . . . 23 10.3 Dynamic Huffman coding . . . . . . . . . . . . . . . . . . . 23 10.4 Factor encoding . . . . . . . . . . . . . . . . . . . . . . . . . 23 10.5 * Parallel Huffman coding . . . . . . . . . . . . . . . . . . . 23 11 Approximate pattern matching 25

11.1 Edit distance—serial computation . . . . . . . . . . . . . . 25 11.2 Longest common subsequence problem . . . . . . . . . . . . 25 11.3 String matching with errors . . . . . . . . . . . . . . . . . . 25 11.4 String matching with don’t care symbols . . . . . . . . . . . 25 11.5 * Edit distance—efficient parallel computation . . . . . . . 25

12 Two-dimensional pattern matching 27 12.1 Multi-pattern approach: Baker and Bird algorithms …. 28 12.2 Periodicity approach: Amir-Benson-Farach algorithm …. 28 12.3 Matching with don’t care symbols, and non-rectangular pat-

terns . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 12.4 Matching with mismatches . . . . . . . . . . . . . . . . . . 28 12.5 Multi-pattern matching . . . . . . . . . . . . . . . . . . . . 28 12.6 Matching by sampling . . . . . . . . . . . . . . . . . . . . . 28 12.7 An algorithm fast on the average . . . . . . . . . . . . . . . 28 12.8 Finding regularities in parallel . . . . . . . . . . . . . . . . . 28 12.9 Simple geometry of 2-dimensional periodicities . . . . . . . 28 12.10* Patterns with large monochromatic centers . . . . . . . . 28 12.11* A version of the Galil-Park algorithm . . . . . . . . . . . 28

13 Time-space optimal string matching 29 13.1 Prelude to factorized string matching . . . . . . . . . . . . . 29 13.2 GS algorithm: search phase . . . . . . . . . . . . . . . . . . 29 13.3 * Preprocessing the pattern: perfect factorization . . . . . . 29 13.4 CP algorithm: search phase . . . . . . . . . . . . . . . . . . 29 13.5 * Preprocessing the pattern: critical factorization . . . . . . 29 13.6 Optimal computation of periods . . . . . . . . . . . . . . . 29

14 Time-processors optimal string matching 31 14.1 Vishkin’s parallel string matching by duels and by sampling 31 14.2 * Galil’s sieve . . . . . . . . . . . . . . . . . . . . . . . . . . 31 14.3 The suffix-prefix matching of Kedem, Landau and Palem . . 31 14.4 A variation of KLP algorithm . . . . . . . . . . . . . . . . . 31 14.5 Optimal two-dimensional pattern matching . . . . . . . . . 31 14.6 Recent approach to optimal parallel computation of witness

tables: the splitting technique . . . . . . . . . . . . . . . . . 31

15 Miscellanies 33 15.1 String-matching by hashing: Karp-Rabin algorithm . . . . . 33 15.2 Efficient tree-pattern matching . . . . . . . . . . . . . . . . 33 15.3 Shortest common superstrings: Gallant algorithm . . . . . . 33 15.4 Cyclic equality of words, and Lyndon factorization . . . . . 33 15.5 Unique decipherability problem . . . . . . . . . . . . . . . . 33 15.6 * Equality of words over partially commutative alphabets . 33 15.7 Hirschberg-Larmore algorithm for breaking paragraphs into

lines . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

16 Exercises 35

17 Bibliography 37

18 Index 39