Exact String Matching Algorithms

1998
Algorithms Total Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
Boyer & Moore 1801 81 107 191 164 168 148 129 106 191 226 139 151
Knuth, Morris & Pratt 1564 48 121 147 109 177 167 123 102 148 141 146 135
Brute Force 1142 53 92 97 71 91 88 86 83 119 125 114 123
Karp & Rabin 659 46 40 50 53 62 51 43 53 61 78 78 44
Turbo Boyer-Moore 585 20 33 51 50 45 53 49 46 71 92 43 32
Morris & Pratt 571 35 54 66 37 42 62 42 41 49 58 51 34
Quick Search 542 34 50 48 32 34 40 45 42 55 61 68 33
Automaton 527 23 52 39 34 37 38 49 53 46 64 51 41
Shift-Or 428 26 35 27 35 35 44 42 34 25 52 35 38
Horspool 384 11 20 20 26 26 25 39 29 57 63 40 28
SMOA 335 8 25 25 43 34 26 23 30 39 36 29 17
Simon 328 12 22 29 29 27 29 33 25 48 35 27 12
Not So Naive 325 14 19 28 20 24 29 25 24 35 41 34 21
Maximal Shift 275 16 20 25 23 18 26 28 20 36 31 14 18
Optimal Mismatch 261 12 20 18 16 21 21 18 20 35 38 24 18
Apostolico & Giancarlo 239 13 16 24 17 24 16 16 19 29 39 18 8
Smith 235 11 16 22 17 14 20 22 23 26 37 18 9
Colussi 234 10 17 16 23 17 27 24 16 24 31 20 9
Zhu & Takaoka 229 9 14 22 13 13 19 25 18 35 33 17 11
Reverse Factor 228 15 21 18 19 21 16 20 15 24 33 16 10
Galil & Giancarlo 217 10 14 14 19 16 23 19 22 23 34 15 8
Two Way 211 8 13 16 15 15 13 16 18 28 38 19 12
Turbo Reverse Factor 210 13 16 16 19 18 14 15 17 18 38 19 7
Reverse Colussi 201 8 12 19 16 23 14 11 19 22 32 14 11
Apostolico & Crochemore 197 8 15 14 14 12 22 20 17 26 24 13 12
Raita 193 9 13 18 16 10 15 13 18 34 31 9 7
AlphaSkip 177 32 31 35 35 27 17
Galil & Seiferas 170 7 11 14 15 15 15 14 12 20 28 14 5
Skip 169 36 26 34 36 22 15
KmpSkip 140 27 14 25 30 27 17
Total 12777 560 888 1074 945 1039 1061 1084 993 1418 1640 1161 903

page d'accueil
home page

Thierry Lecroq