Sunday字符串匹配算法

Sunday算法的基本介绍

字符串匹配的算法其实之前就已经说过一个KMP算法了，不过现在我还是有点儿不理解KMP算法中next数组中的精髓。其实关于字符串匹配的算法基本有以下的四种。BF算法，这个就是我们在说KMP算法中的那个暴力匹配的那个算法。其次就是KMP算法，也就一种比较难以理解的算法。然后是BM算法，据说是KMP算法的优化，不过实在是恐怖，我看着也十分的复杂，根本没有看的兴趣。最后一个就是Sunday算法，且不论这个算法到底怎么样，就凭这个算法的名字也要努力学习吖。Sunday~多暖的名字吖。关键是我听说Sunday算法简单高效易理解！！！

Sunday算法的基本思路

Sunday算法和BM算法稍有不同的是，Sunday算法是从前往后匹配，在匹配失败时关注的是主串中参加匹配的最末位字符的下一位字符。

  • 如果该字符没有在模式串中出现则直接跳过，即移动位数 = 模式串长度 + 1；
  • 否则，其移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。

可以说这个思路是非常的亲民了。

下面举个例子来了解一下Sunday算法:

参考文章：字符串匹配之Sunday算法

由此可见在这个例子中，Sunday算法的效率还是非常高的，不过也可以看出来，Sunday算法也是有一点儿不稳定的。如果每次都发现后面的那个元素和最后一个相同，那么这个就变成了BF暴力匹配的算法了。

代码实现

这里博主使用的是Java，那我就不使用Java，用C++吧，我还是喜欢我的vscode。。。蛤蛤蛤

/**
 * Sunday字符串匹配算法
 */

#include <iostream>
#include <string>
using std::cout;
using std::endl;
using std::string;

const int ASCII_SIZE = 128;

int sunday(string str, string sub) {

    int strLength = str.size();
    int subLength = sub.size();

    int move[ASCII_SIZE]{0};

    for (size_t i = 0; i < ASCII_SIZE; i++) {
        move[i] = subLength + 1;
    }

    for (size_t i = 0; i < subLength; i++) {
        move[sub[i]] = subLength - i;
    }

    int i = 0;
    int j = 0;
    while (i <= strLength - subLength) {
        j = 0;
        while (str[i + j] == sub[j]) {
            j++;
            if (j >= subLength) {
                return i;
            }
        }
        i += move[str[i + subLength]];
    }
    return -1;
}

int main(int argc, char const *argv[]) {
    string str = "BBC ABCDAB ABCDABCDABDE";
    string sub = "ABCDABDE";

    int index = sunday(str, sub);
    // cout << sub << endl;
    // cout << str.substr(index, sub.length()) << endl;
    cout << (sub == str.substr(index, sub.length()) ? "True" : "False") << endl;

    system("pause");
    return 0;
}

代码说明：

  1. ACSII_SIZE和move是什么意思？

    ACSII_SIZE常用的字符有128个（键盘上可以找得到的），还有另外的128个是找不到的，所以这里我们只使用128而不是256。说到Sunday算法规则的时候我们也提到了。每次匹配失败往后移动多少位完全是取决于匹配失败时子串对应的后一个字符。（可以看上面的图进行理解），所以说每个字母都对应了一个移动的位数。我们可以用一个数组来存储移动的位数。比如说字母a要移动六位就是——move[‘a’] = 6 也就是 move[97] = 6（a对应的ascii值是97）

  2. 第一个for循环？

    当字母没有出现的时候，移动位数 = 模式串长度 + 1

  3. 第二个for循环

    当字母出现的时候， 移动位数 = 模式串长度 - 该字符最右出现的位置(以0开始) = 模式串中该字符最右出现的位置到尾部的距离 + 1。不过上面说的是最右出现的位置，这里没有考虑啊。此言差矣，其实考虑了，i是从左到右进行覆盖的，如果出现了重复的字符，move数组里面存放的肯定是最右面的那个字符对应的移动位数。

  4. i, j与while循环

    i表示的指向主串的开始的位置。j表示的指向字符正在匹配的字符的位置。注意：这里i并不是指向当前正在比较的字符的位置。当前主串中正在匹配的字符的位置是i+j。每次匹配失败的时候，i向后面移动相对应的位置。j重置为0重新进行比较。

总结

不得不说，这个Sunday算法真的简单易理解，关键代码还很好写，效率也非常高。这特喵的谁还看那个什么KMP算法啊。那个啥BM算法反向比较致敬韦神我是更不可能去看的了。不管了，反正Sunday算法赛高就完事了。

赏

一枚小菜鸡