title: Understanding the Knuth Morris Pratt(KMP) Failure Function
body: <p>I've been reading the <a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm" rel="nofollow">Wikipedia article about the Knuth-Morris-Pratt algorithm</a> and I'm confused about how the values are found in the jump/partial match table. </p>
  
  <pre><code>  i  |  0  1  2  3  4  5  6
  W[i] |  A  B  C  D  A  B  D
  T[i] | -1  0  0  0  0  1  2
  </code></pre>
  
  <p>If someone can more clearly explain the shortcut rule because the sentence </p>
  
  <blockquote>
    <p>"let us say that we discovered a proper suffix which is a proper prefix and ending at W[2] with length 2 (the maximum possible)" </p>
  </blockquote>
  
  <p>is confusing. If the proper suffix ends at W[2] wouldn't it be size of 3?</p>
  
  <p>Also I'm wondering why T[4] isn't 1 when there is a prefix and suffix of size 1: The A. </p>
  
  <p>Thanks for any help that can be offered. </p>