/**
 * 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);