字符串匹配算法 [未完待续]

题目：

给定两个字符串 A 和 B，请判断 B 是否是 A 的子串，是的话返回 B 在 A 中第一次出现的位置。

例子：

字符串 A（主串）：abbcefgh
字符串 B（模式串）：bce
B 在 A 中第一次出现的位置是 2（从0开始）

暴力算法（Brute Force）

BF 算法是从头开始，把主串和模式串的字符一个一个进行匹配。如果发现不匹配，再从主串的下一位开始。

<?php
namespace app\index\controller;

class Index
{
    /**
     * 时间复杂度 O(mn)
     */
    public function brute_force()
    {
        $main_string    = 'abbcefgh';                // 主串
        $pattern_string = 'bce';                     // 模式串
        $main_len       = strlen($main_string);      // 主串长度
        $pattern_len    = strlen($pattern_string);   // 模式串长度
        $index          = null;                      // 匹配的位置

        // 循环主串
        for ($i = 0; $i < $main_len; $i++) {
            // 循环模式串
            for ($j = 0; $j < $pattern_len; $j++) {
                // 如果模式串当前字符!=主串当前字符，则没必要比较模式串后面的字符，进入下一个主串字符
                if ($main_string[$i + $j] != $pattern_string[$j]) {
                    break;
                }
                // 如果模式串的全部字符匹配，则记录位置
                if ($j == $pattern_len - 1) {
                    $index = $i;
                }
            }
        }
        echo $index;
    } 
}

RK 算法（Rabin-Karp）

RK 算法是暴力算法的改进。
暴力算法对两个字符串的所有字符依次比较，而 RK 算法比较的是两个字符串的 哈希值

<?php
namespace app\index\controller;

class Index 
{
    /**
     * 时间复杂度 O(n)
     */
    public function RK()
    {
        $main_string    = 'abbcefgh';                // 主串
        $pattern_string = 'bce';                     // 模式串
        $main_len       = strlen($main_string);      // 主串长度
        $pattern_len    = strlen($pattern_string);   // 模式串长度
        $index          = null;                      // 匹配的位置
        $pattern_hash   = hash('md5', $pattern_string, false);       // 模式串的hash值

        // 循环主串，每次截取模式串长度的子串，取其hash值，与模式串hash值比较
        for ($i = 0; $i <= $main_len - $pattern_len; $i++) {
            $interception      = substr($main_string, $i, $pattern_len);  // 截取主串的子串
            $interception_hash = hash('md5', $interception, false);  // 取子串的hash值

            // 如果 hash值相等，记录当前主串的位置
            if (hash_equals($interception_hash, $pattern_hash)) {
                $index = $i;
            }
        }
        echo $index;
    }
}

BM 算法 (Bob Boyer & J Strother Moore)

BM算法仍然是字符的比较。BM算法制定了两条规则：坏字符规则、好后缀规则
坏字符规则：子串与模式串不相等的字符，从模式串的右往左开始比较
这里用 主串“GTTATAGCTGGTAGCGGCGAA”，模式串“GTAGCGGCG”来演示更容易理解

 round 1:  GTTATAGCTGGTAGCGGCGAA 坏字符是第9个字符“T”
           GTAGCGGCG
 round 2:  GTTATAGCTGGTAGCGGCGAA 对齐“T”后，坏字符是第13个字符“A”
                  GTAGCGGCG
 round 3:  GTTATAGCTGGTAGCGGCGAA 对齐“A”后，匹配成功
                     GTAGCGGCG

<?php
namespace app\index\controller;

class Index
{
   /**
    * BM算法 (Bob Boyer & J Strother Moore)
    * 时间复杂度 ：最差情况O(mn)，最好情况O(n)
    */
    public function BM()
    {
        $main        = "abbcefgh";               // 主串
        $pattern     = "bce";                    // 模式串
        $main_len    = strlen($main);            // 主串长度
        $pattern_len = strlen($pattern);         // 模式串长度

        $start = 0;                              // while循环从main[0]开始
        $stop  =  $main_len -  $pattern_len;     // while循环到 main[stop] 结束

        // 循环主串
        while ($start <= $stop) {

            // 循环模式串，从后往前(右到左)比较，找出坏字符（即子串中不与模式串相同的字符）
            for ($index = $pattern_len - 1; $index >= 0; $index--) {

                // 如果找到主串的坏字符，记住坏字符，break
                if ($main[$start + $index] != $pattern[$index]) {
                    $badChar = $main[$start + $index];
                    break;
                }
            }

            // 如果完全匹配，返回 start
            if ($index < 0)  return $start;

            // 0表示不能在模式串找到坏字符，1表示可以
            $flag = 0;

            // 跳出上一个for循环后，从右往左寻找坏字符在模式串的对应位置offset
            for ($offset = $index - 1; $offset >= 0; $offset--) {

                // 如果能在模式串找到坏字符，则将其与主串的坏字符对齐
                if (isset($badChar) && $badChar == $pattern[$offset]) {
                    // 计算坏字符产生的位移
                    // 位移后start = 原start+(模式串匹配中断的位置index-坏字符在模式串对应的位置)
                    $start = $start + ($index - $offset);
                    $flag  = 1;
                } elseif ($offset == 0) {
                    // 如果flag等于0 ，则表示循环完模式串仍找不到坏字符，
                    // 直接将模式串移到主串坏字符的下一位
                    if ($flag == 0) {
                        $start += 1;
                    }
                }
            }
        }
        // 没有找到匹配的子串
        return -1;
    }
}

本作品采用《CC 协议》，转载必须注明作者和本文链接