title: KMP Table building algorithm
body: <p>I checked the <a href="http://en.wikipedia.org/wiki/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm#Description_of_pseudocode_for_the_table-building_algorithm" rel="nofollow noreferrer">KMP table-building algorithm from Wikipedia</a> but I don't understand the logic behind the second case of the while loop</p>
  
  <pre><code>(second case: it doesn't, but we can fall back)
          else if cnd &gt; 0 then
              let cnd ← T[cnd]
  </code></pre>
  
  <p>I tried to build a table using this algorithm and it works perfectly. I understand that <code>cnd ← T[cnd]</code> helps to find the proper suffix length. What I don't understand is "how" it does it?</p>
  
  <p>An explanation with an example would be nice.</p>
  
  <p>Thanks!</p>
  
  <p>Edit: I just found out that my question is a duplicate of the question here: <a href="https://stackoverflow.com/questions/18911735/partial-match-table-aka-failure-function-in-kmp-on-wikipedia?rq=1">&quot;Partial match&quot; table (aka &quot;failure function&quot;) in KMP (on wikipedia)</a></p>
  
  <p>I think I get the answer now. Still, one more explanation would be helpful. Thanks!</p>