c++ 字符串匹配算法sunday算法

sunday 算法是一种很高效的字符串匹配算法， 其实现也较kmp算法简单很多

class Sunday {
public:
    const string& needle;
    int mp[300];

    Sunday(const string& needle) : needle(needle) {
        fill(mp, mp + 300, -1);
        for (int i = 0; i < needle.size(); i++) {
            mp[needle[i]] = i;
        }
    }
    int advance(char c) {
        int n = mp[c];
        return (int)needle.size() - n;
    }

    void advance(int& i, int &j, char c) {
        i += advance(c);
        j = 0;
    }

    int strstr(const string& target) {
        int i = 0, j = 0;
        while (i + needle.size() < target.size() + 1) {
            if (needle[j] == target[i + j]) {
                if (++j == needle.size()) {
                    return i;
                }
            } else {
                advance(i, j, target[i + needle.size()]);
            }
        }
        return -1;
    }
};

class Solution {
public:
    int strStr(string haystack, string needle) {
        Sunday sun(needle);
        return sun.strstr(haystack);
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43

c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法
c++ 字符串匹配算法sunday算法