昨天看了阮一峰老师《字符串匹配的KMP算法》的一篇博客，写的非常好。这篇文章也解决了：有一个字符串“BBCABCDABABCDABCDABDE”，它是否包含另一个字符串“ABCDABD”？后来发现，其实这不就是PHP自带的函数strpos的作用吗？于是一时兴起，自己写了一个类来实现这个算法。代码haystack=$haystack;$this->needle=$needle;}//初始化一些参数privatefunctioninit(){$this->_haystackLen=$this->getLen($this->haystack);$this->_needleLen=$this->getLen($this->needle);$this->_matchTable=$this->getMatchTable();$this->_isMatch=false;}//类似strpos函数publicfunctionstrpos(){$this->init();//干草堆$haystackIdx=$matchNum=0;while($haystackIdx<=$this->_haystackLen-$this->_needleLen){//针$needIdx=0;对于(;$needIdx<$this->_needleLen;$needIdx++){如果(strcmp($this->haystack[$haystackIdx],$this->needle[$needIdx])<>0){如果($matchNum>0){$lastMatchValue=$this->getLastMatchValue($needIdx-1);$haystackIdx+=$this->getStep($matchNum,$lastMatchValue);$匹配数=0;}else{$haystackIdx++;}休息;}else{$haystackIdx++;$匹配数++；如果（$matchNum==$this->_needleLen）{$this->_isMatch=true;休息;}}}if($this->_isMatch==true){中断；}}返回$this->_isMatch？$haystackIdx-$this->_needleLen:false;}//获取字符长度privatefunctiongetLen($str){returnmb_strlen($str,'utf-8');}//MatchTableMatchTableprivatefunctiongetMatchTable(){$matchTable=[];对于($i=0;$i<$this->_needleLength;$i++){$intersectLen=0;$nowStr=mb_substr($this->needle,0,$i+1,'utf-8');$preFixArr=$this->getPreFix($nowStr);$sufFixArr=$this->getSufFix($nowStr);如果($preFixArr&&$sufFixArr){$intersectArr=array_intersect($preFixArr,$sufFixArr);如果(!empty($intersectArr)){$intersect=array_pop($intersectArr);$intersectLen=mb_star($intersect,'utf-8');$matchTable[$i]=$intersectLen;}返回$匹配表；}//创建前缀privatefunctiongetPreFix($str){$outArr=[];$strLen=$this->getLen($str);如果($strLen>1){对于($i=1;$i<$strLen;$i++){$outArr[]=mb_substr($str,0,$i,'utf-8');}}返回$outArr;}//获取后缩数据组privatefunctiongetSufFix($str){$outArr=[];$strLen=$this->getLen($str);如果($strLen>1){对于($i=1;$i<$strLen;$i++){$outArr[]=mb_substr($str,$i,null,'utf-8');}}返回$outArr;}//计算步长privatefunctiongetStep($matchNum,$lastMatchValue){return$matchNum-$lastMatchValue;}//获取最后匹配值privatefunctiongetLastMatchValue($index){returnisset($this->_matchTable[$index])?$this->_matchTable[$index]:0;}}$str='BBCABCDABABCDABCDABDE';$subStr='ABCDABD';$kmp=newKMP($str,$subStr);var_dump($kmp->strpos());$kmp->haystack='ibelieve';$kmp->needle='lie';var_dump($kmp->strpos());$kmp->haystack='iloveu';$kmp->needle='hate';var_dump($kmp->strpos());
