Exact String Matching Algorithms

1997
Algorithms Total Jan Feb Mar Apr May Jun Jul Aug Sep Oct Nov Dec
Boyer & Moore 461 10 3 10 7 22 16 1 6 11 99 183 93
Knuth, Morris & Pratt 330 13 13 7 17 19 19 11 10 15 51 77 78
Brute Force 321 20 13 16 6 20 19 8 8 23 65 76 47
Karp & Rabin 207 12 10 6 5 8 16 7 9 4 48 39 43
Quick Search 183 5 5 5 4 8 11 3 4 6 49 49 34
Automaton 180 24 8 9 8 14 11 6 7 10 30 34 19
Turbo Boyer-Moore 156 4 7 8 4 11 7 0 3 3 28 56 25
Shift-Or 148 14 8 5 5 9 12 3 6 8 24 29 25
Morris & Pratt 140 15 7 5 8 4 16 3 6 4 17 26 29
Not So Naive 98 11 6 6 3 6 4 1 7 4 13 31 17
Maximal Shift 89 6 3 5 2 3 6 5 2 3 16 24 14
Simon 89 10 4 6 5 4 5 1 4 4 16 16 14
SMOA 85 3 6 1 3 6 2 1 2 3 21 21 16
Optimal Mismatch 80 3 3 2 2 6 4 3 5 2 17 17 16
Colussi 79 13 4 5 3 3 4 1 3 4 14 14 11
Horspool 79 4 2 4 2 3 6 1 4 3 18 21 11
Apostolico & Giancarlo 73 4 3 5 3 2 4 1 2 2 14 25 8
Reverse Factor 70 10 3 6 1 2 3 1 2 2 14 14 12
Galil & Giancarlo 69 12 5 5 5 1 4 2 3 4 9 13 6
Two Way 67 3 2 3 1 4 3 0 2 3 14 16 16
Apostolico & Crochemore 61 9 3 4 4 3 4 0 3 1 8 16 6
Raita 60 5 3 3 1 4 3 0 2 2 16 16 5
Reverse Colussi 58 6 2 3 2 1 2 0 1 1 17 17 6
Smith 56 5 2 3 1 3 3 1 4 3 9 17 5
Zhu & Takaoka 54 5 3 4 1 1 5 2 3 1 10 11 8
Turbo Reverse Factor 54 10 1 4 1 3 1 0 1 2 15 8 8
Galil & Seiferas 41 4 2 1 1 6 0 0 1 2 9 9 6
Total 3388 240 131 141 105 176 190 62 110 130 661 875 578

page d'accueil
home page

Thierry Lecroq