Exact String Matching Algorithms

2001
Algorithms Total Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
Boyer & Moore 9796 412 426 574 882 892 550 628 582 715 1245 1533 1357
Knuth, Morris & Pratt 6754 333 371 478 582 660 427 333 268 487 888 1128 799
Brute Force 6435 327 340 384 572 565 430 416 326 547 829 978 721
Karp & Rabin 4245 193 216 308 437 442 329 283 199 288 463 636 451
Automaton 3430 168 177 250 310 311 257 238 168 259 423 512 357
Quick Search 3322 152 173 225 301 315 217 199 220 240 415 521 344
Morris & Pratt 2901 169 139 212 275 260 179 189 132 178 370 435 363
Shift Or 2654 117 245 200 230 233 167 166 139 180 316 367 294
Tuned Boyer Moore 2549 114 114 193 240 230 173 174 140 171 295 387 318
Turbo Boyer Moore 2436 107 117 183 253 234 163 161 139 161 303 323 292
Horspool 2131 97 122 151 231 199 133 129 126 160 207 312 264
KmpSkip 2068 91 95 124 208 255 127 134 109 140 256 285 244
Not So Naive 1845 87 92 126 183 172 121 106 107 117 203 313 218
Simon 1844 91 103 135 163 195 137 113 97 133 201 260 216
AlphaSkip 1622 82 91 116 157 166 97 90 95 129 211 200 188
Skip 1474 50 86 113 173 137 103 88 85 116 158 191 174
SMOA 1408 58 73 106 140 140 101 90 82 99 172 196 151
Smith 1375 46 78 114 133 138 105 106 85 94 140 186 150
Zhu & Takaoka 1327 56 85 112 135 143 86 88 90 91 146 154 141
Two Way 1316 53 74 97 152 128 86 100 76 96 149 163 142
Colussi 1264 64 68 95 124 131 82 83 78 94 128 179 138
Optimal Mismatch 1241 68 73 82 145 135 78 69 75 95 156 141 124
Backward Oracle Matching 1230 59 63 105 123 118 89 82 65 104 138 147 137
Apostolico & Giancarlo 1229 55 68 94 132 141 83 79 74 77 142 154 130
Reverse Factor 1208 57 63 79 111 119 78 77 54 96 160 181 133
Apostolico & Crochemore 1178 54 67 93 124 114 81 65 65 78 135 161 141
Maximal Shift 1177 59 73 83 137 110 98 79 66 87 118 135 132
Turbo Reverse Factor 1117 44 65 76 110 127 72 87 70 82 131 132 121
Raita 1080 42 50 87 118 119 75 81 73 64 110 135 126
Galil & Giancarlo 1070 48 59 79 113 112 78 67 57 85 106 140 126
Reverse Colussi 1065 52 70 91 118 111 70 75 58 82 101 135 102
Berry & Ravindran 974 45 58 68 108 101 76 61 66 68 102 122 99
Galil & Seiferas 906 34 43 67 90 88 58 64 54 68 100 136 104
Forward Dawg Matching 575             70 61 74 112 145 113
Backward Nondeterministic Dawg Matching 484             57 47 70 102 119 89
Total 76730 3484 4037 5300 7310 7341 5006 4927 4228 5625 9231 11242 8999

page d'accueil
home page

Thierry Lecroq