Implementing Knuth-Morris-Pratt algorithm

Knuth-Morris-Pratt (KMP) string-matching algorithm is very similar to the naive algorithm we just implemented. The basic difference is that the KMP algorithm uses information from the partial matches and takes a decision to stop matching on any mismatch. It can also precompute the locations where the pattern can exist so that we can reduce the number of repeating comparison or false checks. The KMP algorithm pre-computes a table that helps during the search operation and increases efficiency. While implementing KMP algorithm, we need to computer the Longest Proper Prefix Suffix (LPS). Let's check the function to generate the LPS part:

function ComputeLPS(string $pattern, array &$lps) { 
    $len = 0; 
    $i = 1; 
    $M = strlen($pattern); 

    $lps[0] = 0; 

    while ($i < $M) { 
    if ($pattern[$i] == $pattern[$len]) { 
     ...