KMP算法-PHP实现

简介

今天，我们的主角就是看毛片算法。 哦不，KMP算法,口误口误(内心ps:叫习惯了)

那什么是看毛片算法呢，是用了可以在里面看毛片吗。那当然必须的。。。。不是啦 emmmm，简洁来讲呢就是字符串匹配算法(本文:不是我不想讲清楚，是笔者懒啦) ![b2.gif][2]

很多朋友又会问了，为什么我不用暴力法呢。我是不会解释的，自己google答案(至于怎么google，笔者怎么这么懒，我是不会管的)

好了，上代码

PHP代码实现

```php < │ * │ │ * │ ... ⌒ ... │ * │ │ * └───┐ ┌───┘ * │ │ * │ │ * │ │ * │ └──────────────┐ * │ │ * │ ├─┐ * │ ┌─┘ * │ │ * └─┐ ┐ ┌───────┬──┐ ┌──┘ * │ ─┤ ─┤ │ ─┤ ─┤ * └──┴──┘ └──┴──┘ * 神兽保佑 * 代码无BUG! */ class KMP{ private static $res = '';

public static function bulidNextArray($string){
	$nextArray = [0];
	$key = 0;
	for ($pointer=1; $pointer < strlen($string); $pointer++) { 
		if ($string[$pointer] == $string[$key]) {
			$key++;
		}else{
			while (0 < $key && $string[$pointer] != $string[$key]) {
				$key = $nextArray[$key-1];
			}
		}

		$nextArray[$pointer] = $key;
	}

	return $nextArray;
}

public static function kmpALG($mainString,$minorString,$all = false){
	$mainStringL = strlen($mainString);
	$minorStringL = strlen($minorString);
	$nextArray = self::bulidNextArray($minorString);
	$isFind = false;
	$key = 0;
	$res = self::$res;

	for ($pointer=0; $pointer < $mainStringL; $pointer++) { 
		if ($minorString[$key] == $mainString[$pointer]) {
			$key++;
		}else{
			while (0 < $key && $mainString[$pointer] != $minorString[$key]) {
				$key = $nextArray[$key-1];
			}
		}

		if ($minorStringL == $key) {
			$isFind = true;
			$res = $res.'位置'.($pointer-$minorStringL+1).'//';
			if ($all) {
				$pointer = $pointer-$minorStringL+1;
				$key = 0;
			}else{
				break;
			}
		}
	}
	var_dump($res);exit;
	if (!$isFind) {
		$res = '找不到匹配数据';
	}

	return $res;
}

}

$kmp = new \KMP(); $res = $kmp::kmpALG('ahh,ctexthuang it‘s always been here.ctexthuang','ctexthuang',true); var_dump($res); ?>

emmm,输出是`string(19) "位置4//位置39//"`；



本文为ctexthuang原创文章,转载请注明来自[ctexthuang_blog][1] 


  [1]: https://ctexthuang.com
  [2]: https://qncdn.ctexthuang.com/2020/03/2538170895.gif