Return to Question

replaced http://programmers.stackexchange.com/ with https://softwareengineering.stackexchange.com/

edited Apr 12, 2017 at 7:31

1

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 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 P in T.

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?

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 P in T.

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?

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 P in T.

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?

Tweeted twitter.com/StackSoftEng/status/832020315928682496

occurred Feb 16, 2017 at 0:14

[time-estimation] (and it's synonymous tag [estimations]) is not appropriate for this post.

edit approved Feb 15, 2017 at 21:08

1

c++ algorithms strings time-estimation

Question Protected by gnat

occurred Feb 15, 2017 at 17:13

spelling, formatting, personal stuff cleanup

edited Jan 16, 2013 at 16:34

20.5k
29
117
310

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)O(n+m). I have found that in the worst case scenario Boyer-Moore has an O(nm)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 Answerthis answer

I forgot to mention whatWhat I'm exactly looking for so here it is : Given

Given a text TT and a pattern PP I have to find all the apparencesappearances of PP in TT. Also

Also the length of P and T are from [1,2 000 000] And The[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.Now I am wondering which Which would be best for this type of Pattern Search.pattern search?

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 Answer

I forgot to mention what I'm exactly looking for so here it is : Given a text T and a pattern P I have to find all the apparences of P in T. 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.Now I am wondering which would be best for this type of Pattern Search.

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 P in T.

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?

Update due to Answer

edited Jan 16, 2013 at 16:27

361
1
3
7

Loading

formatting and context

edited Jan 15, 2013 at 21:35

10.2k
1
50
46

Loading

asked Jan 15, 2013 at 20:49

361
1
3
7

Loading