串的模式匹配算法

2021-10-31  本文已影响0人  iOS之文一

数据结构和算法学习汇总

本文主要讲述了串的模式匹配算法，包括BF算法、RK算法、KMP算法、BM算法，使用不同的算法实现目标串查找子串，重点在于分析的过程，通过不同的算法分析提高逻辑思维能力

模式匹配的目的就是在目标串中查找与模式串相等的子串。在这里称呼主串为s，模式串为t，主串的长度为n，模式串的长度为m

(BF)Brute-Force算法

介绍：

暴力算法，将目标串和模式串的每个字符都进行一一比较。性能最差，但是使用最广，因为实现简单，而且在字符串较小的情况下耗费的性能也很小。

核心思想

实现思路

代码实现

#define NOT_FOUND -1
int findStringInString(char *a, char *b) {
    if (!*a || !*b) return NOT_FOUND;
    int i = 0, j;
    char *p;
    while (a[i]) {
        if (a[i] == b[0]) {
            p = a + i; // 当前字符串的开头
            j = 1; // 头已经比较过了，从下一个位置开始比较
            while (p[j] && b[j] && p[j] == b[j]) // 一次比较
                j++;
            if (!b[j]) // 子串完全匹配
                return i;
            if (!p[j]) // 主串已经到末尾了，之后字符串长度都不够，就不需要再比较了
                return NOT_FOUND;
        }
        i++; // 移动字符开始的索引
    }
    return NOT_FOUND;
}

算法分析

O(n*m)

RK算法

介绍：

RK算法把字符串比较问题，转换为了Hash值比较问题。
将模式串t的每个字符的比较改成了将串作为整体与目标串进行哈希值比较，这样就减少了比较次数
以前模式串与子串的比较需要比较每个字符，现在只要整体比较依次哈希值就可以。所以减少了比较次数。

核心思想

算法说明

哈希算法

哈希算法.png

这里我们可以发现一个Hash冲突问题，比如"abc"和"bc"的Hash值是一样的，因为最高位是0。所以还需要进行哈希冲突算法。

哈希冲突算法：

利用前一个结果计算下一个哈希值
这是因为目标串的相邻子串，其实相差的只有第一个字符和最后一个字符，其他字符是相同的，
所以我们可以利用前一个计算结果减去前一个字符串的第一个字符串，加上这个字符串的最后一个字符就够了。

代码实现

#define NOT_FOUND -1

bool isMatch(char *mainStr, int i, char *matchStr, int m) {
    for (int j = 0; j < m; j++) {
        if (mainStr[i+j] != matchStr[j])
            return false;
    }
    return true;
}

int RK(char *mainStr, char *matchStr) {
    int d = 26; // 表示进制
    int n = (int)strlen(mainStr); // 主串长度
    int m = (int)strlen(matchStr); // 子串长度
    
    unsigned int mainHash = 0; // 主串分解子串的哈希值
    unsigned int matchHash = 0; // 模式串的哈希值
    // 1.求得子串与主串中0~m字符串的哈希值[计算子串与主串0-m的哈希值]
    // 循环[0,m)获取模式串A的HashValue以及主串第一个[0,m)的HashValue
    int offset = 'a' - 1; // a为最小值，保证a是最高位时，不会为0
    // 2.计算哈希值同时获取d^m-1值(因为经常要用d^m-1进制值)
    int dm1 = 0;
    for (int i = 0; i < m; i++) { // 小于m，不计算\0的值，数字会小一点
        matchHash = (d * matchHash + (matchStr[i] - offset));
        mainHash = (d * mainHash + (mainStr[i] - offset));
        dm1 = dm1 > 0 ? dm1 * d : 1;
    }
    
    // 3.遍历比较哈希值
    for (int i = 0; i <= n-m; i++) {
        if (matchHash == mainHash // 判断模式串哈希值是否和其他子串的哈希值一致
            && isMatch(mainStr, i, matchStr, m)) // 哈希值相等后，再次用字符串进行比较，防止哈希值冲突
            return i;
        // 计算下一个子串的哈希值
        mainHash = (mainHash - (mainStr[i] - offset) * dm1) * d + mainStr[i+m] - offset;
//        mainHash = (mainHash % dm1) * d + mainStr[i+m] - offset; // 或者取余
    }
    return NOT_FOUND;
}

算法分析

KMP算法

介绍：

针对BF的弊端，在KMP算法中可以进行多字符的跳跃对比，以此来避免目标串的不必要回溯。

例子：

例子.png

简单说明一下：

核心思想

真子串：

匹配：

例如：目标串："abxabcabcaby"，模式串："abcaby"

KMP的算法示意图.png

模式串的最大真子串为ab,
我们在匹配时，发现目标串的子串abcabc与模式串的前字符都匹配，最后一个字符不匹配
所以就从目标串的abcabc的后面abc开始与模式串进行匹配，而不需要匹配前面的abc了。

也就是从上一个a字符直接跳跃到了下一个a字符，而不是从b字符开始。

改进：

会存在一种情况：

实现思想：

BM算法

介绍：

它是一种非常高效的字符串匹配算法，有实验统计，它的性能是著名的KMP算法的三四倍。BM算法的原理很多复杂，比较难懂，学起来比较烧脑。
实现思想和KMP算法基本上是一样的，都是先计算模式串的真子串，之后再查找真子串的大小，当出现不匹配时，直接在真子串后进行匹配，区别于KMP算法，它是从后往前匹配的

这里比上面的KMP算法增加了一个坏字符规则，可以更快的跳跃，当然KMP算法本身也可以使用坏字符规则

匹配顺序.png

核心思想

跳跃位置计算

坏字符规则

坏字符规则.png
说明：

好后缀规则

好后缀规则.png

总结

上一篇下一篇

猜你喜欢

热点阅读