KMP算法簡介：

KMP算法是一種改進後的字符串匹配算法，由D.E.Knuth與V.R.Pratt和J.H.Morris同時發現，因此人們稱它為克努特——莫裡斯——普拉特操作（簡稱KMP算法）。通過一個輔助函數實現跳過掃描不必要的目標串字符，以達到優化效果。

function getNext($string) {
	$next[0] = 0;
	$j = 1;
	$k = 0;
	$strlen = strlen($string);
	while($j < $strlen){
		if($string[$k] == $string[$j]) {
			$next[$j] = $k;
			$j++;
			$k++;
		}else{
			$k = $next[$k];
			if($k == 0) {
				$next[$j] = 0;
				$j++;	
			}
		}
	}
	
	return $next;
}


function kmpSearch($string, $pattern) {
	$len1 = strlen($string);
	$len2 = strlen($pattern);
	$next = getNext($pattern);

	$i = 0;
	$j = 0;
	while($i < $len1){
		if($string[$i] == $pattern[$j]) {
			$i++;
			$j++;
		} else {
			$j = $next[$j];
			if($j == 0) {
				$i++;
			}
		}
		
		if($j == $len2 ){
			echo '子串出現位置：'.($i - $j) .'<br/>';
			$j = $next[$j-1]; //匹配出pattern在string中全部出現位置
		}
	}
}

*