字元串比對算法-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;
}