字符串匹配算法-sunday一种实现

sunday算法的时间效率很高，为了直观，便不算严谨给出时间复杂度，它的最优时间复杂度可以是O(n / m)，n代表母串长度，m代表模式串长度，也就是要查找的单词

文章目录

• 前言
• 一、Sunday是什么？
• 二、代码

前言

Sunday算法思想很简单，将配合图片和代码进行解释，实现方法和思路略有不同

一、Sunday是什么？

当前匹配失败了，对比匹配失败的下一位，以这个位置的字符作为黄金点，在模式串中查找是否有与之相对应的黄金对齐点位，也就是对应的模式串数组坐标

找到了黄金对齐点位之后，从开始进行一一比对，如果也就是匹配失败，继续之前的过程

简单一点来说，就是这样的一个过程，只需要做一部分的准备工作就可以完成整个的过程

二、代码

代码如下

#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <queue>
#include <stack>
#include <map>
#include <set>
#include <string.h>
using namespace std;

int sunday(const char *s, const char *t) {
    int offset[256];
    int n = strlen(t), m = strlen(s);
    for (int i = 0;i < 256; i++) offset[i] = n + 1;
    //一开始默认所有字符都是没有出现过的
    for (int i = 0; t[i]; i++) {
        offset[t[i]] = n - i; 
    }
    //倒数第多少位
    for (int i = 0; i + n <= m; i += offset[s[i + n]]) {
       //之所以每次都是跳跃i += offset[s[i + n]
       //是因为如果最后一个字符串是在模式串中的，那么一定可以找到它的位置
       //相当于模式串向前走了一位
       //如果没有找到这个s[i + n]，那就代表着这个区间上不可能存在这个模式串
        cout << "s[i] "<< s[i]  << " " << i << endl;
        int flag = 1;
        for (int j = 0; t[j] && flag; j++) {
            flag = flag && (s[i + j] == t[j]);
        }
        if (flag) return i;
    }
    return -1;
}

int main() {
    char a[100], b[100];
    cin >> a >> b;
    cout << sunday(a, b) << endl;

    return 0;
}