Hack笔记

前段时间面试的时候，被一个公司的人问到过，今天正好在地铁上面看到了关于KMP算法的文章，作者写的很好，我这个算法渣都看懂了！于是就抽空写了这个PHP版本的kmp算法实现，写的不好的地方欢迎指正。

<?php
/**
 * kmp字符串比较算法
 */

/**
 * 获得所有前缀集合
 * @param string $string
 *
 * @return array
 */
function get_prefix_set($string){
    $len = strlen($string);
    if($len <= 1 ) return [];
    $prefixs = [];
    for($i=1;$i<$len;$i++){
        $prefixs[] = substr($string,0,$i);
    }
    return $prefixs;
}

/**
 * 获得所有后缀集合
 * @param string $string
 *
 * @return array
 */
function get_suffix_set($string){
    $len = strlen($string);
    if($len<=1) return [];
    $suffixs = [];
    for($i=1;$i<$len;$i++){
        $suffixs[] = substr($string,$i);
    }
    return $suffixs;
}

/**
 * 查找字符串$str2是否在$str1中出现
 * @param string $str1
 * @param string $str2
 *
 * @return bool
 */
function my_strstr($str1,$str2){
    $prefixSet = get_prefix_set($str2);
    $suffixSet = get_suffix_set($str2);
    $intersection = array_intersect($prefixSet,$suffixSet);
    $matchValue = 0;
    if(!empty($intersection)){
        foreach($intersection as $tmpstr){
            $len = strlen($tmpstr);
            if($len>$matchValue) $matchValue = $len;
        }
    }
    $str1_len = strlen($str1);
    $str2_len = strlen($str2);
    $endPos = $str1_len-$str2_len;
    if($endPos<0){
        return false;
    }
    for($i=0;$i<=$endPos;){
        $moveStep = 1;
        for($n=0;$n<$str2_len;$n++){
            if($str1[$i+$n] != $str2[$n]){//字符串不匹配时,跳出本次循环
                $moveStep = $n-$matchValue;
                $moveStep = $moveStep > 0 ? $moveStep : 1;
                break 1;
            }else if($str1[$i+$n] == $str2[$n] && $n==$str2_len-1){
                return true;
            }
        }
        $i +=$moveStep;
    }
    return false;
}

$result = my_strstr("abcabfcde","bfcd");
var_dump($result);

如果对KMP算法不是特别了解可以看一下《字符串匹配的KMP算法》。