example consider the pattern "amalgamationfrom figure the knuth-morris-pratt (kmpfailure functionf ( )for the string is as shown in the following tablek [kf ( implementation our implementation of the kmp pattern-matching algorithm is shown in code fragment it relies on utility functioncompute kmp faildiscussed on the next pageto compute the failure function efficiently the main part of the kmp algorithm is its while loopeach iteration of which performs comparison between the character at index in and the character at index in if the outcome of this comparison is matchthe algorithm moves on to the next characters in both and (or reports match if reaching the end of the patternif the comparison failedthe algorithm consults the failure function for new candidate character in por starts over with the next index in if failing on the first character of the pattern (since nothing can be reused def find kmp(tp) """return the lowest index of at which substring begins (or else - "" nm len( )len(pintroduce convenient notations if = return trivial search for empty string rely on utility to precompute fail compute kmp fail( = index into text = index into pattern while if [ = [ ] [ : +kmatched thus far if = match is complete return + try to extend match + elif fail[ - reuse suffix of [ : else + return - reached end without match code fragment an implementation of the kmp pattern-matching algorithm the compute kmp fail utility function is given in code fragment