constructing the kmp failure function to construct the failure functionwe use the method shown in code fragment which is "bootstrappingprocess that compares the pattern to itself as in the kmp algorithm each time we have two characters that matchwe set jk note that since we have throughout the execution of the algorithmf ( is always well defined when we need to use it def compute kmp fail( ) """utility that computes and returns kmp fail list "" len(pby defaultpresume overlap of everywhere fail [ = = while mcompute (jduring this passif nonzero if [ = [ ] characters match thus far fail[jk + + elif follows matching prefix fail[ - elseno match found starting at + return fail code fragment an implementation of the compute kmp fail utility in support of the kmp pattern-matching algorithm note how the algorithm uses the previous values of the failure function to efficiently compute new values performance excluding the computation of the failure functionthe running time of the kmp algorithm is clearly proportional to the number of iterations of the while loop for the sake of the analysislet us define intuitivelys is the total amount by which the pattern has been shifted with respect to the text note that throughout the execution of the algorithmwe have < one of the following three cases occurs at each iteration of the loop if jp[ ]then and each increase by and thuss does not change if  [kand then does not change and increases by at least since in this case changes from to ( )which is an addition of ( )which is positive because ( if  [kand then increases by and increases by since does not change