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

题目:

给定两个字符串 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 协议》,转载必须注明作者和本文链接
讨论数量: 0
(= ̄ω ̄=)··· 暂无内容!

讨论应以学习和精进为目的。请勿发布不友善或者负能量的内容,与人为善,比聪明更重要!