title: What is the purpose of the second while loop in KMP when building the partial match table?
body: <p>When building the partial match table for KMP:</p>
  
  <pre class="lang-c prettyprint-override"><code>void buildBackTable() { 
      int i = 0, j = -1; b[0] = -1; 
      while (i &lt; m) { 
          while (j &gt;= 0 &amp;&amp; P[i] != P[j]) j = b[j]; //Why is this a while loop!?
          i++; j++;
          b[i] = j;
      }
  }   
  </code></pre>
  
  <p>How come that second while loop is not a conditional instead? Such as:</p>
  
  <pre class="lang-c prettyprint-override"><code>void buildBackTable() { 
      int i = 0, j = -1; b[0] = -1; 
      while (i &lt; m) { 
          if (j &gt;= 0 &amp;&amp; P[i] != P[j]) j = b[j]; //Why not?
          i++; j++;
          b[i] = j;
      }
  }   
  </code></pre>
  
  <p>In most of the examples I've tried, this statement is used to reset j to -1 when there is no match, so when the next iteration comes, we compare the first character of the string (P[j]) with the character at position i (P[i]).</p>