I think it's obvious that reverse() is a lot slower than search(). reverse() has to allocate memory, then copy every char in the string, and then hash it into the string table.
A standard textbook Boyer-Moore implementation would on average have to go through half the haystack string, so it should (on average) be four times faster than reverse(): Reading n/2 chars vs reading and writing n chars. If search() is any slower than that (barring perhaps some extra startup overhead) then we should toss the implementation asap.
