PHP implémente l'algorithme KMP

function cal_next($str){
    $next[0] = -1;//next[0]初始化为-1

    $i=0;    $j = -1;    $len=strlen($str);    while($i<$len){ 
           if($j===-1 || $str[$i]===$str[$j]){            $i++;            $j++;            $next[$i]=$j;
        }else{            $j=$next[$j];
        }
    }    return $next;
}$str=&#39;ABCDABD&#39;;$next=cal_next($str);
var_dump($next);function search($str,$search){
    $next=cal_next($search);    $i=0;    $j=0;    $lenStr=strlen($str);    $lenSearch=strlen($search);    while($i<$lenStr && $j<$lenSearch){
            if($j===-1 || $str[$i]===$search[$j]){
            //$i 主串的不后退，移动模式串。为什么没有$j===0，因为如果有$j++为1，下一步是判断$str[$i]===$search[1]，跳过了$search[0]
            $i++;            $j++;
        }else{            $j=$next[$j];
        }
    }    if($j===$lenSearch){        return $i-$j;
    }    return -1;
}


var_dump(search($str,&#39;ABD&#39;));

Référence

[KMP算法（1）：如何理解KMP](https://segmentfault.com/a/1190000008575379)

[字符串匹配的KMP算法](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)

 [KMP算法最浅显理解](https://blog.csdn.net/starstar1992/article/details/54913261)

          

function cal_next($str){
    $next[0] = -1;//next[0]初始化为-1

    $i=0;    $j = -1;    $len=strlen($str);    while($i<$len){        if($j===-1 || $str[$i]===$str[$j]){            $i++;            $j++;            $next[$i]=$j;
        }else{            $j=$next[$j];
        }
    }    return $next;
}$str=&#39;ABCDABD&#39;;$next=cal_next($str);
var_dump($next);function search($str,$search){
    $next=cal_next($search);    $i=0;    $j=0;    $lenStr=strlen($str);    $lenSearch=strlen($search);    while($i<$lenStr && $j<$lenSearch){        if($j===-1 || $str[$i]===$search[$j]){//$i 主串的不后退，移动模式串。为什么没有$j===0，因为如果有$j++为1，下一步是判断$str[$i]===$search[1]，跳过了$search[0]
            $i++;            $j++;
        }else{            $j=$next[$j];
        }
    }    if($j===$lenSearch){        return $i-$j;
    }    return -1;
}


var_dump(search($str,&#39;ABD&#39;));

Référence

[KMP算法（1）：如何理解KMP](https://segmentfault.com/a/1190000008575379)

[字符串匹配的KMP算法](http://www.ruanyifeng.com/blog/2013/05/Knuth%E2%80%93Morris%E2%80%93Pratt_algorithm.html)

 [KMP算法最浅显理解](https://blog.csdn.net/starstar1992/article/details/54913261)

Recommandations associées :

PHP implémente des codes de vérification d'addition et de soustraction

php implémente une calculatrice simple

PHP implémente un simple verrouillage de document Redis et empêche les appels répétés simultanés

Ce qui précède est le contenu détaillé de. pour plus d'informations, suivez d'autres articles connexes sur le site Web de PHP en chinois!