KMP算法与朴素匹配

查找算法中朴素匹配之于KMP就类似冒泡排序之于快速排序

 function KMPMatch($src, $par) {
    $K = array(0);
    $M = 0;
    for($i=1; $i<strlen($str); $i++) {
        if ($str[$i] == $str[$M]) {
            $K[$i] = $K[$i-1] + 1;
            $M ++;
        } else {
            $M = 0;
            $K[$i] = $K[$M];
        }
    }
    for($i=0,$j=0; $i<strlen($src); ) {
        if ($j == strlen($par)) return $i-$j;

        if ($par[$j] === $src[$i]) {
            $j++;
            $i++;
        } else {
            if ($j === 0 && $par[$j] != $src[$i]) {
                $i++;
            }
            $j = $K[$j-1 >= 0 ? $j -1 : 0];
        }
     }
     return false;
 }

 function normalSearch($src, $par) {
     for($i=0; $i< strlen($src); $i++) {
         $k = $i;
         $j = 0;
         while($i<strlen($src) && $j<strlen($par) && $par[$j] == $src[$k]) {
             $k++;$j++;
         }
         if ($j == strlen($par)) return $k - $j;
     }
     return false;
 }

匹配内容包含较多重复字符时KMP算法明显比朴素匹配要快.