KMP算法-PHP实现

简介

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

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

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

好了,上代码

PHP代码实现

<?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

tag(s): 算法
show comments · back · home
Edit with markdown
召唤看板娘