title: When would you use KMP over BOYER-MOORE
body: <p>I am currently learning about pattern matching algorithms and have come across these two algorithms. I have the following general ideas:</p>
  
  <p>KMP</p>
  
  <ul>
  <li>Compares text left-to-right</li>
  <li>Uses a failure array to shift intelligently</li>
  <li>takes O(m), where m is the length of the pattern, to compute failure array</li>
  <li>takes O(m), space</li>
  <li>takes O(n), time to search a string</li>
  </ul>
  
  <p>BM</p>
  
  <ul>
  <li>Compares pattern from last character</li>
  <li>Uses bad character jumps and good suffix jumps</li>
  <li>takes O(m + size of alphabet) to compute tables</li>
  <li>takes O(m + size of alphabet), space</li>
  <li>takes O(n), but usually better to search</li>
  </ul>
  
  <p>I came across the following question which triggered this question(True or False):</p>
  
  <blockquote>
    <p>The Knuth-Morris-Pratt (KMP) algorithm is a good choice if we want to
    search for the same pattern repeatedly in many different texts.</p>
  </blockquote>
  
  <p>So I believe the answer is true just because the assumption is that every time you run the algorithm on different text the preprocessing is only O(n) where for BM it is O(n + size of alphabet). However, I am not sure if I am making the correct assumption that every time the algorithm is rerun a new table is recomputed. Because say the text always falls in the alphabet of english. I would only need to compute the table once and just reuse the table. So at the end of the day, would the answer to this question be dependent on the fact that the algorithms are all being run on text which is contained in the same alphabet or is there some other factor which may affect it?</p>