title: string matching with finite automata
body: <p>I am reading about string algorithms in Cormen's book "Introduction to Algorithms". For Transition which is shown below. </p>
  
  <p>My question: why are we doing <code>min(m+1, q+2)</code> and why are we incrementing m by 1 and q by 2. </p>
  
  <p>Following link has back ground to above question.</p>
  
  <p><a href="http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Fall2009/StringMatching.pdf" rel="nofollow">http://people.scs.carleton.ca/~maheshwa/courses/5703COMP/Fall2009/StringMatching.pdf</a></p>
  
  <p>Kindly help here with a simple example.</p>
  
  <pre><code>Algorithm Compute-Transition-Function(P, Sigma)
  m = length(P);
  for  q = 0 through m  do
     for each character  x  in Sigma
         k = min(m+1, q+2);
         repeat  k = k-1  // work backwards from q+1
         until  Pk 'is-suffix-of' Pqx;
         d(q, x) = k; // assign transition table
     end for;
  end for;
  
  return  d;
  End algorithm.
  </code></pre>