今天，我们的主角就是看毛片算法。 哦不，KMP算法,口误口误(内心ps:叫习惯了)
那什么是看毛片算法呢，是用了可以在里面看毛片吗。那当然必须的。。。。不是啦
emmmm，简洁来讲呢就是字符串匹配算法(本文:不是我不想讲清楚，是笔者懒啦)
b2.gif
很多朋友又会问了，为什么我不用暴力法呢。我是不会解释的，自己google答案(至于怎么google，笔者怎么这么懒，我是不会管的)
好了，上代码
emmm,输出是string(19) "位置4//位置39//"；
/**
* 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);