Exact String Matching Algorithms

2002
Algorithms Total 1997 1998 1999 2000 2001 Jan Feb Mar Apr May Jun Jul Aug
Boyer & Moore 26933 461 1801 2980 2284 9796 1092 971 1648 1328 1457 1277 1083 755
Brute Force 20648 321 1142 3072 1653 6435 801 704 1150 1122 1080 1120 1110 938
Knuth, Morris & Pratt 19465 330 1564 2925 2007 6754 645 537 1024 919 947 736 608 469
Karp & Rabin 12247 207 659 1669 1407 4245 457 473 726 623 545 472 422 342
Automaton 9533 180 527 1247 1027 3430 371 351 453 456 411 405 327 348
Quick Search 9375 183 542 1267 842 3322 352 381 455 433 415 388 415 380
Morris & Pratt 8179 140 571 1123 881 2901 316 274 446 364 335 286 290 252
Shift Or 7462 148 428 989 812 2654 306 297 373 349 299 296 254 257
Turbo Boyer Moore 6979 156 585 1029 682 2436 259 229 319 269 284 279 250 202
Horspool 6145 79 384 794 618 2131 291 241 301 335 260 276 235 200
Tuned Boyer Moore 5731     334 638 2549 263 243 366 293 295 296 240 214
Not So Naive 5190 98 325 723 568 1845 219 171 248 246 232 195 164 156
Simon 5194 89 328 736 562 1844 217 189 235 234 219 203 166 162
KmpSkip 4970 0 140 551 555 2068 238 189 253 259 212 175 181 149
AlphaSkip 4504 0 177 653 512 1622 202 208 263 234 194 159 147 133
Skip 4204 0 169 649 398 1474 233 189 212 194 179 164 175 168
SMOA 4131 85 335 609 442 1408 150 159 211 170 157 149 128 128
Smith 3747 56 235 479 375 1375 165 162 189 174 162 134 131 110
Optimal Mismatch 3651 80 261 603 437 1241 125 122 178 151 121 118 113 101
Colussi 3636 79 234 519 412 1264 146 128 158 161 154 135 120 126
Two Way 3613 67 211 502 387 1316 154 138 169 159 138 145 124 103
Zhu & Takaoka 3603 54 229 469 370 1327 163 141 160 155 146 159 117 113
Apostolico & Giancarlo 3530 73 239 461 421 1229 129 96 154 155 160 154 155 104
Reverse Factor 3515 70 228 452 345 1208 158 133 178 164 165 141 138 135
Maximal Shift 3448 89 275 448 384 1177 156 129 164 147 149 116 115 99
Apostolico & Crochemore 3400 61 197 481 401 1178 132 102 205 150 139 132 118 104
Turbo Reverse Factor 3203 54 210 454 384 1117 135 109 159 128 121 120 98 114
Galil & Giancarlo 3108 69 217 448 381 1070 129 102 142 130 115 116 93 96
Raita 3067 60 193 452 337 1080 121 101 143 151 117 128 82 102
Reverse Colussi 2968 58 201 404 329 1065 109 88 132 121 133 123 108 97
Backward Oracle Matching 2742       411 1230 134 135 151 172 153 134 115 107
Galil & Seiferas 2667 41 170 379 319 906 102 100 134 117 101 112 102 84
Berry & Ravindran 2190       306 974 121 107 134 137 108 123 87 93
Forward Dawg Matching 1558         575 138 97 135 135 136 122 114 106
Backward Nondeterministic Dawg Matching 1327         484 118 96 120 112 105 110 94 88
Total 215853 3388 12777 27891 21887 76730 8847 7892 11488 10447 9944 9198 8219 7135

page d'accueil
home page

Thierry Lecroq