Exact String Matching Algorithms

2000
Algorithms Total Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
Boyer & Moore 2284 9 21 74 151 99 111 172 74 231 400 524 418
Knuth, Morris & Pratt 2007 11 23 64 148 117 114 130 71 148 303 431 438
Brute Force 1653 21 26 65 115 89 106 132 79 143 273 338 266
Karp & Rabin 1407 13 15 40 90 82 102 101 67 106 254 301 236
Automaton 1027 13 15 35 61 53 85 83 61 85 171 196 169
Morris & Pratt 881 11 12 34 87 38 66 77 52 63 114 162 165
Quick Search 842 4 12 52 55 64 56 77 50 67 138 131 136
Shift Or 812 12 14 43 78 65 55 71 49 50 109 123 143
Turbo Boyer Moore 682 7 17 38 43 35 49 55 43 58 112 104 121
Tuned Boyer Moore 638 0 7 39 44 33 53 61 24 56 103 97 121
Horspool 618 4 11 24 40 30 33 44 30 47 129 112 114
Not So Naive 568 7 10 14 41 26 45 53 33 45 82 106 106
Simon 562 8 11 18 43 26 31 55 37 35 104 90 104
KmpSkip 555 2 6 19 36 32 46 63 24 42 92 85 108
AlphaSkip 512 5 9 19 30 25 45 49 41 50 82 73 84
SMOA 442 2 13 14 25 23 35 53 20 23 74 76 84
Optimal Mismatch 437 5 12 16 26 37 29 37 24 19 82 75 75
Apostolico & Giancarlo 421 4 8 21 31 20 31 38 27 34 69 64 74
Colussi 412 9 8 17 28 18 26 41 26 22 58 80 79
Backward Oracle Matching 411 0 9 25 23 20 33 49 26 34 58 65 69
Apostolico & Crochemore 401 4 10 15 32 14 30 43 24 28 72 62 69
Skip 398 5 10 17 23 18 30 37 27 25 70 63 73
Two Way 387 1 9 21 27 14 25 36 16 23 76 61 78
Maximal Shift 384 3 6 13 25 22 34 33 24 28 67 63 66
Turbo Reverse Factor 384 3 8 23 24 17 27 31 26 40 54 62 69
Galil & Giancarlo 381 7 13 14 30 12 22 37 20 28 63 64 69
Reverse Factor 375 3 11 20 18 18 22 41 18 29 52 48 65
Smith 375 3 8 17 25 16 32 40 19 28 61 65 61
Zhu & Takaoka 370 2 9 15 23 19 29 44 19 29 59 59 63
Raita 337 4 7 14 23 21 26 40 18 20 58 47 59
Reverse Colussi 329 2 9 16 20 18 19 37 16 26 55 43 68
Galil & Seiferas 319 2 9 13 22 17 19 33 13 24 53 56 58
Berry & Ravindran 306 0 3 16 23 13 22 34 16 23 47 47 62
Total 21887 186 371 885 1510 1151 1488 1936 1114 1709 3594 3973 3970

page d'accueil
home page

Thierry Lecroq