KMP算法-PHP实现

简介

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

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

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

好了，上代码

PHP代码实现

/**
 * Created by sublime.
 * Author: ctexthuang
 * Date: 2019-12-10
 * Time: 12:26
 * FileName: test.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