failureFunction(P):
|  Input  pattern P of length m
|  Output failure function for P
|
|  F[0]=0                  // F[0] is always 0
|  j=1, len=0
|  while j<m do
|  |  if P[j]=P[len] then
|  |     len=len+1         // we have matched len+1 characters
|  |     F[j]=len          // P[0..len-1] = P[len-1..j]
|  |     j=j+1
|  |  else if len>0 then   // mismatch and len>0?
|  |     len=F[len-1]      //  → use already computed F[len] for new len
|  |  else                 // mismatch and len still 0?
|  |     F[j]=0            //  → no prefix of P[0..j] is also suffix of P[1..j]
|  |     j=j+1             //  → continue with next pattern character
|  |  end if
|  end while
|  return F