title: Relation between KMP algorithm and Z algorithm
body: <p><code>KMP</code> and <code>Z</code> algorithms are well known algorithms for string searching,</p>
  
  <p><code>KMP</code> algorithm deals with finding the patterns through a KMP failure function which is defined as (<code>pat</code> being the searching pattern)</p>
  
  <blockquote>
    <p>lps[i] = the longest proper prefix of pat[0..i] which is also a suffix of pat[0..i]. </p>
  </blockquote>
  
  <p>e.g for <code>string "abcab"</code> it would be <code>[0, 0, 0, 1, 2]</code></p>
  
  <p>where as <code>Z</code> algorithm uses the z function which is defined as:</p>
  
  <blockquote>
    <p>Given a string S of length n, the Z Algorithm produces an array Z where Z[i] is the length of the longest substring starting from pat[i] which is also a prefix of pat.</p>
  </blockquote>
  
  <p>Now the question is can we achieve the <code>Z</code> function by the use of <code>KMP</code> algorithm?
  What I am searching for is some modifications in the <code>lps</code> array that leads to the same results as the <code>Z[i]</code> array.</p>