Algorithms on strings

Half-title......Page 3
Title......Page 5
Copyright......Page 6
Contents......Page 7
Preface......Page 9
1 Tools......Page 11
Alphabet and strings......Page 12
Languages......Page 14
Automata......Page 15
Some specific strings......Page 18
Periodicity and borders......Page 20
Powers, primitivity, and conjugacy......Page 26
Writing conventions of algorithms......Page 28
Pattern matching algorithms......Page 29
Some standard objects......Page 31
Full implementations......Page 33
Reduced implementations......Page 35
A complete example......Page 36
Notion of sliding window......Page 38
The naive algorithm......Page 39
Heuristics......Page 40
Search engine......Page 42
Bit-vector model......Page 46
Table of borders......Page 50
Table of prefixes......Page 52
Relation between borders and prefixes......Page 56
Notes......Page 57
Exercises......Page 58
2 Pattern matching automata......Page 65
2.1 Trie of a dictionary......Page 66
2.2 Searching for several strings......Page 67
Dictionary automaton......Page 68
Construction of the dictionary automaton......Page 69
Output of the occurrences......Page 73
Implementation by transition matrix......Page 74
Definition of the implementation......Page 75
Searching phase......Page 77
Construction of the implementation......Page 79
Optimization of the failure function......Page 80
2.4 Implementation with successor by default......Page 82
Size of the implementation......Page 83
Construction of the implementation......Page 85
Searching phase......Page 87
Challenge of implementations......Page 89
2.5 Locating one string......Page 92
Properties of the optimized failure function......Page 95
Implementation of the failure functions with tables......Page 96
Searching phase......Page 98
Construction of the implementation......Page 102
Searching phase......Page 104
Challenge of implementations for searching for one string......Page 106
Notes......Page 108
Exercises......Page 109
3 String searching with a sliding window......Page 112
3.1 Searching without memory......Page 113
Searching phase......Page 115
Weak version......Page 117
3.2 Searching time......Page 118
3.3 Computing the good suffix table......Page 123
Algorithm......Page 124
Complexity of the computation......Page 127
3.4 Automaton of the best factor......Page 128
3.5 Searching with one memory......Page 131
Searching phase......Page 132
Running time of the searching phase......Page 134
3.6 Searching with several memories......Page 137
Searching phase......Page 138
Complexity of the searching phase......Page 142
3.7 Dictionary searching......Page 146
Exercises......Page 151
4 Suffix arrays......Page 156
Interval problem......Page 157
Membership problem......Page 158
4.2 Searching with the longest common prefixes......Page 160
4.3 Preprocessing the list......Page 165
4.4 Sorting suffixes......Page 168
4.5 Sorting suffixes on bounded integer alphabets......Page 174
4.6 Common prefixes of the suffixes......Page 179
Notes......Page 184
Exercises......Page 185
5 Structures for indexes......Page 187
5.1 Suffix trie......Page 188
Suffix links......Page 191
5.2 Suffix tree......Page 194
5.3 Contexts of factors......Page 203
Suffix function......Page 205
Evolution of the congruence......Page 206
5.4 Suffix automaton......Page 209
Size of the automaton......Page 210
Suffix link and suffix paths......Page 212
Online construction......Page 214
Complexity......Page 219
5.5 Compact suffix automaton......Page 220
Notes......Page 224
Exercises......Page 226
6.1 Implementing an index......Page 229
6.2 Basic operations......Page 232
Position......Page 234
List of positions......Page 236
6.3 Transducer of positions......Page 237
6.4 Repetitions......Page 240
6.5 Forbidden strings......Page 241
6.6 Search machine......Page 244
Lengths of the common factors......Page 245
Optimization of the suffix link......Page 248
6.7 Searching for conjugates......Page 249
Notes......Page 250
Exercises......Page 251
7 Alignments......Page 253
Edit distance and edit operation......Page 254
Alignments......Page 257
Edit graph......Page 258
Dotplot......Page 260
7.2 Optimal alignment......Page 261
Computation of the edit distance......Page 262
Computation of an optimal alignment......Page 265
Computation of all the optimal alignments......Page 269
Automaton of the optimal alignments......Page 270
7.3 Longest common subsequence......Page 272
Computation by dynamic programming......Page 273
Computation of the length in linear space......Page 276
Computation of a longest subsequence in linear space......Page 277
7.4 Alignment with gaps......Page 283
7.5 Local alignment......Page 286
Similarity......Page 287
Computation of an optimal local alignment......Page 288
7.6 Heuristic for local alignment......Page 289
Notes......Page 292
Exercises......Page 294
8 Approximate patterns......Page 297
Jokers only in the string......Page 298
Jokers in the text and in the string......Page 300
Dynamic programming......Page 303
Diagonal monotony......Page 304
Partial computation......Page 307
Diagonal computation......Page 308
Execution time of the diagonal computation......Page 312
Search automaton......Page 314
Specific implementation......Page 315
Complexity of the searching phase......Page 318
Merge......Page 319
Correctness proof......Page 321
Exact string matching......Page 324
One mismatch......Page 327
One insertion......Page 329
One deletion......Page 331
Short patterns with differences......Page 332
8.5 Heuristic for approximate pattern matching with differences......Page 334
Notes......Page 338
Exercises......Page 339
9.1 Partitioning factors......Page 342
9.2 Detection of powers......Page 350
Computation of local powers......Page 351
Number of occurrences of local powers......Page 353
9.3 Detection of squares......Page 355
Existence of a square......Page 356
Number of prefix or factor squares......Page 361
Incremental computation of the ranks of the suffixes......Page 364
Computation of the common prefixes......Page 367
Notes......Page 368
Exercises......Page 369
Collections of articles......Page 374
Applications......Page 377
Articles......Page 378
Index......Page 387