|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Smyth B. — Computing patterns in strings |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
Leech, John 74
Lefebvre, Arnaud 24 102 105
Left-extendible see "LE"
Leftmost position (in string) 4—5 7
Lempel, Abraham 40 157 175—178 350
Length (of string) 7—8
Lentin, Andre 20 329 339
letter 6
Levenshtein, V.I. 44
Lewis, Harry R. 295
Lexicographic order 8 12 100 128—129 133 135 170—172
Li, Yin xii 57 89 360—370
Local optimality (of approximate squares) 381 385 388—390 395
Longest common factor see "LCF"
Longest common prefix see "LCP" "lcp"
Longest common subsequence see "LCS" "lcs"
Longest common suffix 342 344 353
Loop, invariant 23 158 162—163 202 270 356
Loop, variant 23
Lorentz, Richard J. 51 329—331 340—350 393—395
Lothaire, M. x 85
Lowest common ancestor see "LCA"
Lowrance, Roy 243
Lu, Weilin 24 85 102 105
Lyndon, decomposition 28—33 40 157—167 173—174
Lyndon, Roger C. 29 158
Lyndon, word 28—31 33 157—170 173
Lyngso, Rune B. 357 375
Main, Michael G. 40 51 56 329—331 340—349 350—356 381 393—395
Manber, Udi 149—156 205 279 286—292 305—308 315—316 375
Margaritis, Konstantinos G. 231
Masek, William J. 264 274
Match, approximate 237—293 380—396
Match, exact 181—235
Match, false 199 201
Mauri, G. 149
Maximal periodicity see "Run"
Maximal repetition see "Run"
McCreight, Edward M. 113 116—121 138 154
McFaddin, Scott 391
McNaughton, Robert F. 304
McNulty, George F. 74
Meidanis, Joao ix
Meltzer, A. 213
Metacharacter 46—48 237 289—290 298—299 308
Metric 45 238 241 259 266 398 402
Michailidis, Panagiotis D. 231
Mignosi, Filippo 22 85
Miller, Dianne 95 100
Minimum starting point 1
Moore, Dennis xii 84 95 100 334 365
Moore, J. Strother 23 42 127 187—198 206—225 231—235 273 297 309 313—314 325
Morphism 61—65 71—77 80 85—86
Morphism, block of 72—75
Morphism, identity 63
Morphism, initiator of 72—73
Morphism, inverse 63—64
Morphism, iteration of 62—64
Morphism, terminator of 72—73
Morris, James H. 42 181—187 194 235
Morrison, Donald R. 37
Muth, Robert 316
Muthukrishnan, S. 127
Myers, Gene W. 149—156 256—264 276 279—286 302 375 395 401
Nagy, Benedek 202
Navarro, Gonzalo ix 266 285 292—293 297 309 317—326
NDFA 297—308 310
NE, array see "Array"
NE, repeat see "Repeat"
NE, tree see "Tree"
Necklace 4 25—33 59 62 90 157 174
Necklace, infinite 4
Needleman, Saul B. 241
NLE, array see "Array"
NLE, repeat see "Repeat"
NLE, tree see "Tree"
Non-left-extendible see "NLE"
Non-right-extendible see "NRE"
Nondeterministic finite automaton see "NDFA"
Nonextendible see "NE"
Normal form 10—11 13—14 23 35—36 52—53 93 111 158 161—162 195—196 221 331 338 347 365
Normal form, right 14 196 221
NRE, array see "Array"
NRE, repeat see "Repeat"
NRE, tree see "Tree"
Occurs 8 267
Odlyzko, Andrew M. 14 194
On (an alphabet) 6
On-line 19 39 90—91 93 99 104—105 121 125 126 139 166 174 177 234 241 369—370
Optimal alignment (of strings) 238
Overlap (of substrings) 9 54 66—67 328 339 357 362 381 390 395
p-canonical 95—101 103 107 166
P-equivalence 94—95 100—101
Palindrome 13 71
Papadimitriou, Christos H. 295
Parikh, Rohit J. 348
Park, James 391
Park, Kunsoo 263—264 279 396—402
Paterson, Michael S. 164 234 264 274
Path score (in grid graph) 386—388
Pattern 42
Pattern, approximate 43—51 57—58 180 237—293 315—326 380—402
Pattern, generic xi 51—59 327—402
Pattern, intrinsic xi 35—41 109—178
Pattern, multiple 46—49 295—326
Pattern, specific x 41—51 179—326
Pattern-equivalence see "p-equivalence"
Pattern-free 26 32—33 51 61—62 64 72—75 86 330 350
pattern-matching see "Pattern"
Pavesi, G. 149
Pederson, Christian N.S. 56 357 375 379
Period 10—11 13—24 26—27 52 55 58—59 162 194—196 219—221 224 227 335 339 347 351 353—355 358 362—363 365—366 370
Period, "the" 10
Period, approximate 51 58 328 396—402
Period, array 370
Period, minimum 10
Period, tree 370
Period, trivial 10
Periodic 11
Periodic, 3-periodic 195—197 210 221
Periodic, strongly 11 13 67
Periodic, weakly 11 13
periodicity 14—24 26 51 111 161 195 197 219 328 350 359—402
Periodicity Lemma 20—22 24 32 111 358 363
Periodicity, maximal see "Run"
Perleberg, Chris H. 273
Perrin, Dominique 234
Petho, Attila xii
Pinzon, Yoan J. 264
Plandowski, Wojciech 223 225 313
Pleasants, Peter A.B. 62
Plouffe, Simon 95
Position in a string 7—8
Position, nodes (in suffix tree) 372—374 377—378
Position, tree 140 175
Pratt, Vaughan R. 42 181—187 194 235
Predecessor (in a string) 4—5 7—8
Prefix 9
Prefix, node (in suffix tree) 116—117 119 124—126
Prefix, proper 8—9
Prefix-preserving 66 68 77 79
Preparata, Franco P. 38 329 391
primitive 11 13 22 26 28 32—33 158—160 162 170—171 355
Processing time see "Execution time"
Quasiperiod(ic) 57 328 359
Rabin, Michael O. 199—202
Raman, Rajeev 53
Randall, Jim 75
Rauzy, Gerard 85
Re 55—56 59 370
| Reachable (in an FA) 301 303 307
Refinement (in Crochemore's algorithm) 332—340 348
Regnier, Mireille 194 211
Regular, expression 46—49 180 237 286 291 295 297—309
Regular, set 48
Reichert, Thomas A. 241
Reid, James F. 264
REPEAT 53—57
Repeat, approximate 57—58 348 360 380—396
Repeat, complete 53—54 370—375
Repeat, mixed 54
Repeat, NE 55 57 357 360 370—375 379—380
Repeat, NLE 371—372 374
Repeat, NRE 371—372
Repeat, split 54 56 357
Repeat, tandem 54—55 59 329 379—380
Repeating substring 53
Repeating substring, maximal NE 373
Repetition 11 51—52 329—358
Repetition weak 59 62
Repetition, approximate 58 238 381—382
Repetition-free 26 32—33 51 86
Repetitive 11
Restivo, Antonio 22
Right extension 39 364—366 369
Right-extendible see "RE"
Rightmost position (in string) 4—5 7
Rivest, Ronald L. 233
Rotation (of string) 25—28 31—33 50 55 59 75 79—82 84 111 158 160 197 222 347 362—363
Rote, Guenter 85
Run 56 78 82—86 328—329 331 347 349—358 360 382
Run, leftmax 353 358
Run, leftmost 349—356
Run, rightmax 353 355
Ryan, Patrick J. xii 17 24 102 105
Rytter, Wojciech ix 193 223 225 313
s-factorization 40 157 175—178 349—352 355—358
Sadakane, Kunihiko 150 154
Sakoe, Hiroaki 241
Sankoff, David 241
Schensted, Craige 264
Schmidt, Jeanette P. 263—264 380—396 401
Schuetzenberger, Marcel P. 20 329 339
Score (of approximate match) 381 384—388 390—394
Scoring matrix 44 241 243—244 381 384 397 401
Sedgewick, Robert 150 154
Seebold, Patrice 85
Seiferas, Joel 113 141 234
Sellers, Peter H. 381 388
Sentinel ($) 36 115 121 140 149 174 186 189 198
Sequence of iterates 62—64
Sequence, big (in Crochemore refinement) 334—335 337
Sequence, small (in Crochemore refinement) 334—338
Sethi, Ravi 305
Setubal, Joao ix
Shallit, Jeffrey 75
Shift, cyclic see "Rotation"
Shift, long (in Boyer — Moore) 195—196 221
Shift, safe 191
Shift, short (in Boyer — Moore) 195—196 221
Shift, Type I (in Boyer — Moore) 190—191 196—197 222—223
Shift, Type II (in Boyer — Moore) 191 195—196 220
Shiloach, Yossi 174
Shinohara, A. 149
Shrdlu, Etaoin 218
Signature (in Karp — Rabin) 199—200
Sim, Jeong Seop 396—402
Simpson, R. Jamie xii 13 32 70—71 84 349—350 357 363
Sink (in DAWG) 142 144
Sink (in FA) see "State accepting"
Skip loop 208—209 213 215 217—219 232
Sloane, N.J.A. 95
Slowscan 117 119—121 137 139
Smartscan 124—126
Smit, G. de V. 185 194
Smith, Temple F. 384
Smyth, Jocelyn xii
Source in FA see "State start"
Source in grid graph 386—389
Source in suffix tree 138 147—148
Space complexity 90—91 204 233—235 241 246 292 391
Square 11
Square, abelian 62
Square, approximate 381 383 390—391 393 395
Square, NE 67 69 71
Square, new (in Algorithm ML) 341 344
Square, newleft (in Algorithm ML) 342 344 349 353
Square, newright (in Algorithm ML) 342—343 348—349 353
Square, overlapping 381 390 395
Square, regular (in Thue strings) 70
Square, split 381 390—391
Square, tandem 381 390—391 393—396
Square-free 61—62 72—75
Stable sort 128
Staircase (of covers) 364 366—369
State (of a computation) 202—204 295—320
State (of a computation), accepting 298—301 303 308 310—311 314
State (of a computation), active 317—320
State (of a computation), start 297—299 301—302 308
State (of a computation), vector 265 269 271
Stephen, Graham A. ix
Stolarsky, Kenneth B. 85
Stoye, Jens 38 357 375
String 4—14
String, b-canonical 100—108
String, circular see "Necklace"
String, coverable 54 56 59 360 379—380
String, empty 5—8
String, Fibonacci see "Fibostring"
String, finite 7
String, infinite 4—6 9 61—87
String, initial 62 64 71 86—87
String, linear 4—14
String, p-canonical 94—100
String, Sturmian 85
String, text 42 47 49 187 193 195 199 205 209 212 233 265—267 269 279 284—285 297 300 302 304—305 307—309 312—313 315—318 323—324
String, Thue 51 62—75 77 93—94
Subsequence 45
Subsequence, longest common see "LCS"
Substitution 43—45 50 240 242—244 269 274 287 289 291 317—318 320
Substitution, rule see "Morphism"
Substring 8
Substring, coverable 54 56 360 379
Substring, dead (in cover algorithm) 364—369
Substring, live (in cover algorithm) 364—369
Substring, proper 8
Substring, repeating see "Repeating substring"
Subword tree see "Suffix tree"
Successor (in a string) 4—5 7—8
Suffix 9
Suffix tree 36—39 90 111 113—150 155—157 176—177 264 273 279 296 298 304 310 330—331 339—340 356—357 360 370—380
Suffix tree, linked 5
Suffix tree, traversal of see "Fastscan" "Slowscan" "Smartscan"
Suffix, array 40 111 149—156 370—372 375—380
Suffix, function 116 126 138 141 143 145
Suffix, proper 9
Suffix, tree see "Suffix tree"
Sun, Yu 24 102 105
Sunday, Daniel M. 209 212—219 231—232
Superstring 8
Superstring, proper 8
Swanson, Kurt 113
Syntax tree see "Tree"
Szymanski, Thomas G. 250—256 264
Tail (of run) 56 82
Tail (of suffix) 115 118—119 138
Takeda, Masayuki 149
Tang, Yudong 370—380
Tarhio, Jorma 273
Tarjan, Robert Endre 135
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå