札记之PHP实现BM算法

暴力匹配（BF）算法是普通的模式匹配算法，BF算法的思想就是将目标串S的第一个字符与模式串T的第一个字符进行匹配，若相等，则继续比较S的第二个字符和T的第二个字符；若不相等，则比较S的第二个字符和T的第一个字符，依次比较，直到得出最后的匹配结果。

问题

有两个字符串，S1是母串，S2是子串，要在母串中找子串出现的位置。

S1：WANGDENGKE
S2：KE

思路

• 用s1[i]和s2[j]去匹配，如果匹配成功，i++，j++，即S1和S2都后移一位，匹配下一位；
• 如果匹配失败，让i=i-j+1；j=0；即让S1后移一位，S2回溯，从S1的下一位重新匹配；

PHP代码实现

class BF
{
    function bfSearch($str, $targetStr)
    {
        $strLen = strlen($str);
        $targetLen = strlen($targetStr);

        for ($i = 0, $j = 0; $i < $strLen && $j < $targetLen;) {
            //如果当前字符匹配成功（即S[i] == T[j]），则i++，j++   
            if ($str[$i] == $targetStr[$j]) {
                $i ++;
                $j ++;
            } else {
                //如果失配（即S[i]! = P[j]），令i = i - (j - 1)，j = 0 
                $i = $i - $j + 1;
                $j = 0;
            }
        }
        //匹配成功，返回模式串p在文本串s中的位置，否则返回-1
        if ($j == $targetLen) {
            return ['begin' => $i - $targetLen + 1, 'end' => $i];
        } else {
            return -1;
        }
    }

    function match()
    {
        $str = 'WANGDENGKE';
        $targetStr = 'KE';
        var_dump($this->bfSearch($str, $targetStr));
    }
}

$BF = new BF();
$BF->match();

运行结果

array(2) {
	'begin' =>
  		int(9)
  	'end' =>
  		int(10)
}