1 in each inner loop iteration; the inner loop condition is cnd ≥ 0. This means that the inner loop can execute at most as many times in total, as the outer loop has executed – each decrease of cnd by 1 in the inner loop needs to have a corresponding increase by 1 in the outer loop. Since the outer loop takes iterations, the inner loop can take no more than iterations in total. Combined, the outer and inner loops take at most iterations. This corresponds to time complexity using the Big O notation. Efficiency of the KMP algorithm Since the two portions of the algorithm have, respectively, complexities of O(k) and O(n), the complexity of the overall algorithm is O(n + k). These complexities are the same, no matter how many repetitive patterns are in W or S. Variants A real-time version of KMP can be implemented using a separate failure function table for each character in the alphabet. If a mismatch occurs on character in the text, the failure function table for character is consulted for the index in the pattern at which the mismatch took place. This will return the length of the longest substring ending at matching a prefix of the pattern, with the added condition that the character after the prefix is . With this restriction, character in the text need not be checked again in the next phase, and so only a constant number of operations are executed between the processing of each index of the text. This satisfies the real-time computing restriction. Booth's algorithm uses a modified version of the KMP preprocessing function to find the lexicographically minimal string rotation. The failure function is progressively calculated as the string is rotated. Notes References External links String Searching Applet animation An explanation of the algorithm and sample C++ code by David Eppstein Knuth-Morris-Pratt algorithm description and C code by Christian Charras and Thierry Lecroq Explanation of the algorithm from scratch by H.W. Lang Breaking down steps of running KMP by Chu-Cheng Hsieh. NPTELHRD YouTube lecture video LogicFirst YouTube lecture video Proof of correctness Transformation between different forms of algorithm Knuth-Morris-Pratt algorithm written in C# Knuth-Morris-Pratt string-searching algorithm (part I) + my homebrew algorithms formally verified using CBMC, Knuth-Morris-Pratt string-searching algorithm (part II): DFA version, Knuth-Morris-Pratt string-searching algorithm (part III): DFA-less version KMP algorithm search time complexity explained in plain English String matching algorithms