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