I implemented the Boyer–Moore–Horspool substring-search algorithm in Arc[1].
I then plugged it into my playlist program, and, well... see for yourself:
;; Arc posmatch: 38,236 ms
;; Boyer–Moore–Horspool: 6,396 ms
Wow. I think this confirms that the biggest bottleneck in my program was posmatch[2].
Keep in mind, though, Boyer-Moore isn't always faster than posmatch[3]: due to the preprocessing time, long pattern strings will cause the algorithm to perform slower.
This only applies when the string is preprocessed multiple times: if it's only used once, then the overhead should be negligible. And if you want to use the same pattern string multiple times, you can preprocess it once and then reuse it:
(let x (boyer-moore-process "foobarquxcorgenou")
(boyer-moore-search x "adadadadadadadadadadadad")
(boyer-moore-search x "adadadadadadadadadadadad")
...
(boyer-moore-search x "adadadadadadadadadadadad"))
In general, though, Boyer-Moore is faster. Especially for multi-string searches, which is what my playlist program does.
