PHP

（1）字符串模式匹配

代码

function isStr($str1, $str2)
{
    $str2_len = strlen($str2);
    $str1_len = strlen($str1);
    $isExist  = false;
    $num      = 0;

    for ($i = 0; $i < $str2_len; $i = (($p != 0) ? $p : $i + 1)) {
        $isExist = true;
        $offset  = $i;
        $p       = 0;

        //debug
        $num++;
        echo "第{$num}次=>offset->({$i})<br/>";

        for ($j = 0; $j < $str1_len; $j++) {
            if ($str1{$j} != $str2{$offset++}) {
                $isExist = false;
                break;
            }

            if ($p == 0 && $j > 0 && $str1{0} == $str2{$offset - 1}) {
                $p = $offset - 1;
            }
        }

        if ($isExist) {
            break;
        }
    }

    return $isExist;
}

测试

$str1 = 'ABCDABD';
$str2 = 'BBCABCDABABCDABCDABDE';
var_dump(isStr($str1, $str2));

结果

第1次匹配=>offset->(0)
第2次匹配=>offset->(1)
第3次匹配=>offset->(2)
第4次匹配=>offset->(3)
第5次匹配=>offset->(7)
第6次匹配=>offset->(8)
第7次匹配=>offset->(9)
第8次匹配=>offset->(13)
bool(true)

结束

可以看到打印的结果并没有每次回溯都是向后匹配偏移+1，而是每次偏移的位置会随着上次匹配的记录并标识出当前跳转的offset 而改变，这样省略了很多无用的比较，直到最后匹配成功或者失败。