I have been stuck for some time on which is the fastest string search algorithm, heard many opinions, but in the end I'm not sure.
I have heard some people saying that the fastest algorithm is Boyer-Moore and some saying that Knuth-Morris-Pratt is actually faster.
I have looked up for the complexity on both of them but they mostly look the same
O(n+m). I have found that in the worst case scenario Boyer-Moore has an
O(nm) complexity compared to Knuth-Morris-Pratt which has O(m+2*n). Where n=length of text and m=length of pattern.
As far as I know Boyer-Moore has a linear-worst case-time if I would use the Galil Rule.
My question, Over all which is actually the fastest String search algorithm (This question includes all possible sting algorithms not just Boyer-Moore and Knuth-Morris-Pratt).
Edit: Due to this answer
What I'm exactly looking for is:
Given a text
T and a pattern
P I have to find all the appearances of
Also the length of P and T are from
[1,2 000 000] and the program has to run under 0.15 sec.
I know that KMP and Rabin-Karp are enough to get a 100% score on the problem but I for one wanted to try and implement Boyer-Moore. Which would be best for this type of pattern search?