https://leetcode.com/problems/find-the-index-of-the-first-occurrence-in-a-string

Source

    int strStr_STD(string haystack, string needle) {
        int idx = haystack.find(needle);
        if (idx == std::string::npos) return -1;
        return idx;
    }

    int strStr_Rabin_Karp(string haystack, string needle) {
        const int key_hash = hash(needle);
        const int key_size = needle.size();
        if (key_size <= haystack.size()) {
            for (int i=0; i<haystack.size()-key_size+1; ++i) {
                const string hs = haystack.substr(i, key_size);
                if (key_hash == hash(hs)) {
                    return i;
                }
            }
        }
        return -1;
    }
    int hash(string str) {
        int sum = 0;
        for (const auto c : str) {
            sum += c-'a';
        }
        return std::hash<std::string>{}(str)*sum;
    }

    int strStr_KMP(string haystack, string needle) {
        /*/
        vector<int> lps = kmp_prepare(needle);
        return kmp_search(haystack, needle, lps);
        /*/
        vector<int> lps = longest_proper_suffix(needle);
        return kmp_process(haystack, needle, lps);
        //*/
    }

    vector<int> longest_proper_suffix(const string &P) {
        const int p = P.size();
        vector<int> lps(p, 0);
        for (int i=1, len=0, lim=INF; i < p &&lim>0;--lim) {
            if (P[i] == P[len]) {
                lps[i++] = ++len;
            } else if (len > 0) {
                len = lps[len-1];
            } else {
                lps[i++] = 0;
            }
        }
        return lps;
    }
    int kmp_process(const string &T, const string &P, const vector<int> &lps) {
        const int t = T.size();
        const int p = P.size();
        if (t==0) return 0;

        for (int i=0, j=0, lim=INF; i < t &&lim>0;--lim) {
            if (T[i] == P[j]) {i++, j++;}
            if (j == p) return i-j;
            if (i < t && T[i] != P[j]) {
                j ? j = lps[j-1] : i++;
            }
        }

        return -1;
    }

    vector<int> kmp_prepare(const string &P) {
        const int p = P.size();
        vector<int> lps(p+1, 0);
        lps[0] = -1;
        int j=-1;
        for (int i=0, lim=INF; i < p &&lim>0;--lim) {
            for(;j>=0 && P[i] != P[j] &&lim>0;--lim) {
                j = lps[j];
            }
            ++i; ++j;
            lps[i] = j;
        }
        return lps;
    }
    int kmp_search(const string &T, const string &P, const vector<int> &lps) {
        const int t = T.size();
        const int p = P.size();
        int idx = -1;
        for (int i=0,j=0, lim=INF; i < t &&lim>0;--lim) {
            for (;j >= 0 && T[i] != P[j]&&lim>0;--lim) {
                j = lps[j];
            }
            ++i, ++j;
            if (j == p) {
                idx = i-j;
                j = lps[j];
                break;
            }
        }
        return idx;
    }

GitHub

• StrStr