|
|
 |
| Àâòîðèçàöèÿ |
|
|
|
| Ïîèñê ïî óêàçàòåëÿì |
|
|
|
|
|
|
|
 |
|
|
|
| Smyth B. — Computing patterns in strings |
|
|
|
| Ïðåäìåòíûé óêàçàòåëü |
 -equivalence (in DAWGs) 141 143—145 155
Aggarwal, Alok 391
Agrep 289
Aho, Alfred V. 16 46 176 199 305 309—313 341
Algorithms, ACFA 309—313
Algorithms, ADBG 269—274
Algorithms, BM 187—198
Algorithms, BMFAST 208—209
Algorithms, BMG 219—223
Algorithms, BMGS 220—223
Algorithms, BMH 210—212
Algorithms, BMS1 213—215
Algorithms, BMS2 215—218
Algorithms, BMS2* 217—218
Algorithms, Border 14—20
Algorithms, BYN 317—326
Algorithms, C 331—340
Algorithms, calcLP 344—347
Algorithms, calcLP' 344—347
Algorithms, calcR 353—355
Algorithms, CWFA 313—314
Algorithms, DBG 202—205
Algorithms, DFA 302—305
Algorithms, Dvl 158—167
Algorithms, Dvl* 162—167
Algorithms, Easy 42
Algorithms, F 126—136
Algorithms, FST 370—380
Algorithms, H1 245
Algorithms, H2 246—248
Algorithms, H3 248—249
Algorithms, HS 250—256
Algorithms, KK 356—258
Algorithms, KMP 181—187
Algorithms, KMP* 184—185
Algorithms, KMPH 226—231
Algorithms, KR 198—201
Algorithms, LS 360—370
Algorithms, LZ 175—178
Algorithms, M 279—286
Algorithms, M* 285
Algorithms, MaxSuff 170—174
Algorithms, McC 117—121
Algorithms, MinSuff 167—170
Algorithms, ML 340—349
Algorithms, Mn 350—356
Algorithms, NDFA 297—302
Algorithms, S 380—396
Algorithms, SAComplex 149—156
Algorithms, SANaive 149—156
Algorithms, SASimple 149—156
Algorithms, SIPS1 399—401
Algorithms, SIPS2 401
Algorithms, TD 140—149
Algorithms, Turbo-BM 223—225
Algorithms, U 276—279
Algorithms, Ukn 121—126
Algorithms, UM 256—263
Algorithms, WF 241—244 266—269
Algorithms, WM 286—292 315—316
Algorithms, WM* 305—308
Allison, Lloyd 202 264
Allouche, Jean-Paul 75 85
Alphabet 6—7 61—62 91—92
Alphabet, binary 6 26 39 62 194
Alphabet, general see "Unordered"
Alphabet, indexed 39 92 94 113 126 136 188 190 198 302 304—305 308 312 314 316—317 325 331—332 348 380 384
Alphabet, ordered 6 8 27—33 39 41 46 92 113 120—121 126 157 170 187 198 250 253 256 330—332 339 349
Alphabet, quaternary 6
Alphabet, standard 95
Alphabet, ternary 6 62
Alphabet, unordered 6 92 94 139 175 329 332 341
Amoux, Pierre 85
Andersson, Ame 113
Antecedent 63—64
Apostolico, Alberto 37—38 56 113 174 222 256 329 361 379 391
Arikawa, S. 149
Arlazarov, V.L. 264 302
Array, benefit 381 383—386 388—391 395
Array, border 15—20 23—24 36 52—53 57 91—93 100—108 111—112 182 191—192 309—312 342 359—360 362 364 366—367
Array, cost 239—245 256 263 265—268 274—276 285 381—383 400—401
Array, cover 36 57 91 359—370
Array, Monge 391—393
Array, NE 375—380
Array, NRE 378—380
Array, right border 23 192
Array, suffix see "Suffix"
Astoorian, Dan 75
Asymptotic complexity 8 12 14 22 32 211 256 285 290—291 325
Asymptotically optimal 19 24 91 136 381
Atallah, Mikhail J. 391
Avoidance problem 61—62 67 69 74—75 78 85
Avoidance problem, weak 62
b-canonical 100—108
B-equivalence 100—108
Backtracking 19 90—91 158 161—162 222 227 234 384
Baeza-Yates, Ricardo ix 42 185 194 202—205 211 264 271 273 285 292 297 309 317—326
Baghdadi, Leila xii
Base-pairs 42
Bean, Dwight R. 74
Benefit array see "Array"
Benson, Gary 395
Bentley, Jon L. 150 154
Berstel, Jean 85 363
Binary letter comparison 164
Block (of a morphism) see "Morphism"
Blumer, Anselm 141
Blumer, Janet 141
Boasson, Luc 363
Booth, Kellogg S. 174
Border 9—24 36 66—67 79 100—108
Border, array see "Array"
Border, longest 9 13—16 19 22—23 36 66 75 93 103 106 111 162 182 184 190 192 217 220—221
Border, tree see "Tree"
Border-equivalence see "b-equivalence"
Boshernitzan, M. 85
Bowsher, S. 185
Boyer, Robert S. 23 42 127 187—198 206—225 231—235 273 297 309 313—314 325
Branch nodes 38 121 125 376—378
Braunholtz, C.H. 69 71 74
Breslauer, Dany 361
Brodal, Gerth S. 56 357 375 379
Caelli, Terry xii
Canonical form (of necklace) 27—28 31 33 40 90 158 174—175
Castelli, M. Gabriella 22
Chang, William I. 277—279 285 293
Chappie, Jerry xii
Charras, Christian 181 231
Chen, K.T. 29 158
Chen, M.T. 113 141
Chiba, Seibi 241
Cluster property 151 153 156
Code 63—64 71 75 80
Cohen, Donald N. 241
Cole, Richard 91 164 194—195 234 293
Collision 200
Colussi, Livio 234
Commentz-Walter, Beate 313—314
complexity see "Asymptotic complexity"
Concatenation 4—7 73 126 158
conjugate 65—68 71 173
Corasick, Margaret 309—313
Cost (of edit operation) 239—245 256—259 381—385
Cost, array see "Array"
Cover 54 56—57 59 359—370
Cover of a necklace 59
Cover, array see "Array"
Cover, tree see "Tree"
Coverable see "String"
Crawford, Tim 53
| Crochemore, Maxime ix 40 51 55 138 141 149 174 193 223 225 233—234 264 273 313 329—340 350 360 379 382
cube 11 62 67 69 78—79 81—84
Currie, James D. 32 74
Cyclic shift see "Rotation"
Czumaj, Artur 223 225 313
D-run 376—377 380
Dag 145—148
Davies, G. 185
DAWG 40 111 140—150 155 225
de Luca, Aldo 85
Decomposition 9 40 157 397
Decomposition, Lyndon see "Lyndon"
DELETE see "Deletion"
Deletion 43—45 50 239—241 258—259 289 291 317 384
Dependency graph 257—259 263 381 386
Deterministic finite automaton see "DFA"
DFA 302—305
Difference matrix 279—281
Differences (in Myers' algorithm), horizontal 279 281 283
Differences (in Myers' algorithm), vertical 279 281
Dinic, E.A. 264 302
Directed acyclic graph see "DAG"
Directed acyclic word graph see "DAWG"
Distance (between strings) 43—46 57—58 238 259 266
Distance (between strings), absolute 397
Distance (between strings), asymmetric edit 50
Distance (between strings), deletion 50
Distance (between strings), edit 44 50 237—238 244 264 269 274—277 279—280 284—286 288 292 309 316—317 323—324 383 395—397 401—402
Distance (between strings), Hamming 43 58 237—238 241 269 271 273 292 309 317 362 402
Distance (between strings), Levenshtein 43—45 50 58 237—239 244—245 250 257 263 264 266—268 279—280 286 288—289 309 317
Distance (between strings), relative 397—400
Distance (between strings), weighted 44 50 237—238 266 397—398
Dix, Trevor I. 202 264
Doemoelki, Balint 42 202—205 264
Duval, Jean-Pierre 24 28 102 105 157—175
Dynamic-programming 238—239 381—385 401
Edit operations 43—44 50 238 242—244 268 384 386 395 see "Indel" "Insertion" "Substitution"
Ehrenfeucht, Andrzej 56 74 141 285 379
El-Mabrouk, Nadia 273
Element 3—5
Encoding 13 52—53 55 77—78 82—84 90 93 166 329 347 382
Equal (of strings) 8 12
Erdos, Pal 62
Erickson, Brian W. 381 388
execution time 7 18 90—91 165—166 207
Execution time, amortized 93 105 112
Execution time, average-case 152 165 174 194 201 206 211 225 232—235 276—277 279 285 292—293 323
Execution time, worst-case 22 24 39 42 62 77 90 150 152 162 164—166 174 185 187 194—195 201 206—207 209 211 218—220 225—226 232—235 250 253 264 273 276—277 279 285—286 293 303 305 307 313—314 323 329 332 358 382
EXPONENT 10—11 13 20 36 52—54 61—62 347 350 381
Exponent, "the" 10
Exponent, maximum 10
Exponent, trivial 10
FA 38 296—314 317—326
Factor 9 31 158 351—352 355—356 358 398 400—401
Factorization see "Decomposition"
Failure function algorithm 16 310
Farach, Martin 113—114 126—136 361
Faradzev, I.A. 264 302
Fastscan 117 119—120 124—125 137 139
Fibonacci string see "Fibostring"
Fibostring 52—53 56 58—59 62—64 66 71 76—87 93—94 108 112—114 175—177 185
Fibostring, generalized 78
Fibostring, infinite 77 79
Fibostring, infinite generalized 79
Fibostring, reverse 86
Fine, N.J. 20
Finite automaton see "FA"
Fischer, Michael J. 241—244
Flipflop variable 246
Four Russians technique 264 302
Fox, R.H. 29 158
Fraenkel, Aviezri S. 85 349—350 357
Frangk, Frantisek xii 24 85 102 105 340 347 370—380
Galil, Zvi 91 164 219—220 234 273 279
Gao, Shudi 24 102 105 108
Gap (between repeats) 54 56 338—339 360—361
Gasieniec, Leszek 223 225 313
Generator 10—11 13 52—55 57 158—163 328—329 339 353 355 357 372
Generator, "the" 10
Generator, approximate 360 381—382 396—402
Generator, trivial 10
Giancarlo, Raffaele 91 164 222 234 273
Giegerich, Robert 126
Golden mean 77 108
Gonnet, Gaston H. 42 194 202—205 211 264 271 273 285
grep 46
Grid graph 381 386—395
guard 212—213 218—219 232
Guerra, C. 256
Guibas, Leo J. 14 194
Gusfield, Dan ix 38 177 331 357 375
Hamming, Richard 43
Hancart, Christophe ix 193 223 226—231
Hannan, Sampath K. 395
Harel, Dov 135
Hariharan, Ramesh 91 164 234 293
Hash function 199—200
Haton, Jean-Paul 241
Haussler, David 141 285
Head (of suffix) 115—116 118—121 138
Herendi, Tamas 75
Hirschberg, Dan S. 46 244—250 264
Holub, Jan 149
Hopcroft, John E. 16 46 176 199 299 341
Horspool, R. Nigel 210—212 232
Hoshino, H. 149
Huang, Xiaoqiu 238 382
Hume, Andrew 209 213 217—218 231—232
Hunt, James W. 250—256 264
I-run 376—377
ID-run see "I-run" "D-run"
Iliopoulos, Costas S. xii 53 84 174 264 331 361 396—402
Indel 258—259 267 269 274
Inenaga, S. 149
Initiator (of morphism) see "Morphism"
Insert see "Insertion"
insertion 43—45 50 239—240 258—259 289 291 317 320 384
Iteration (of morphism) see "Morphism"
Jacobson, Guy 264
Jarominek, Stefan 223 225
Jennings, Christopher G. 212
Jiang, Jiandong 22 85
K-approximate match see "Match"
k-differences problem 274—286 289 292
k-mismatches problem 269—274 285—286 289
Karaman, Ayse 85
Karp, Richard M. 46 198—201
Keraenen, Veikko 62
Kim, Sung-Ryul 263—264
Knuth, Donald E. 18 20 36 42 77 97 98 108 176 181—187 194 235 330
Kolpakov, Roman 56 84 331 349—350 356—358
Kosaraju, S. Rao 357
Kowalski, G. 213
Kronrod, M.A. 264 302
Kruskal, Joseph B. 241
Kucherov, Gregory 56 84 331 349—350 356—358
Kurtz, Stefan 126 138 149
Lampe, Jordan 277—279 285
Landau, Gad M. 263—264 273 279 285 395 401
Larmore, Lawrence 391
Larsson, N. Jesper 113 150 154
Lawler, Eugene L. 285 293
LCA 114 130—131 135—136 139
LCF 51 137 140
LCP 129 131 135 151—155 342 344 371—380
LCP, LCP tree see "Tree"
lcp, nodes (in suffix tree) 372—374 378—380
LCS 249—250
LE 55—56 58—59 71 370 389
Lecroq, Thierry ix xii 24 102 105 181 193 223 225 231 233 235 313
|
|
|
| Ðåêëàìà |
|
|
|
|
|
Î ïðîåêòå