Sunday字符串匹配

引入

Sunday 算法是一种极其容易理解的算法，复杂度较为玄学。

事实上，这个算法没啥用

实现

Sunday算法的实现只比暴力匹配多了一个步骤，它在匹配失败时关注的是主串中参与匹配的最末尾字符的下一位字符，分为两种情况：

该字符没有在模式串中出现过，移动位数=模式串长度+1

该字符在模式串中出现过，移动位数=模式串中该字符最右出现的位置（以0开始）到尾部的距离+1 。

举个栗子，假定现在要在主串 substringsearchingxiaowu 中查找模式串 search

刚开始时，将两个字符串的左边对齐

结果是在第二个字符串处发现不匹配，此时关注文本串中参与匹配最末位字符的下一位字符，即绿色的字符 i ，因为模式串中并不存在 i ，所以将模式串直接跳过一大片，享有移动位数=6（模式串长度）+1=7，从 i 之后的那个字符 n 开始下一步匹配

结果第一个字符就不匹配，再看文本串中参与匹配最末位的下一位字符 r ，它出现在模式串倒数第三位，于是把模式串向有移动三位（ r 到模式串末尾的距离+1为3）使两个 r 对齐

匹配成功

基本代码实现（在母串 str 中寻找子串 patten ）：

#include <iostream>
using namespace std;
const int inf = 0x3f3f3f3f;

string str, patten;

int p[256];

signed main() {
    cin >> str >> patten;
    int len1 = str.length(), len2 = patten.length();

    for (int i = 0; i < 256; ++i)
        p[i] = len2 + 1; //先全部初始化，如果字符不存在，直接移动len2+1的长度

    for (int i = 0; i < len2; ++i)
        p[patten[i]] = len2 - i;

    int ans = 0, i = 0;

    while (i <= len1 - len2) {
        int j = 0, temp = i;

        while (patten[j++] == str[temp++] && j < len2); //尝试匹配

        ans += (j == len2); //如果j==len2,是说明有找到,ans++
        i += p[str[i + len2]]; //移动
    }

    cout << ans; //输出答案
    return 0;
}