implement_strstr.cc

// https://leetcode.com/problems/implement-strstr

class Solution {
public:
    // Brute force, O((m - n) * n) worst and average case, O(n) best case
    int strStrNaive(const string& text, const string& pattern) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

        for (int i = 0; i <= m - n; i++)
            if (text.substr(i, n) == pattern)
                return i;

        return -1;
    }

    // Knutt-Morris-Pratt (KMP), O(m + n) worst case, O(m) average and best case
    int strStrKMP(string& text, string& pattern) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

        vector<int> lps(n, 0);

        // preprocessing
        for (int i = 1, len = 0; i < n;)
            if (pattern[i] == pattern[len])
                lps[i++] = ++len;
            else if (len)
                len = lps[len - 1];
            else
                lps[i++] = 0;

        // matching
        for (int i = 0, j = 0; i < m;) {
            if (text[i] == pattern[j]) i++, j++;

            if (j == n) return i - j;

            if (i < m && text[i] != pattern[j])
                j ? j = lps[j - 1] : i++;
        }

        return -1;
    }

    // Rabin-Karp, O(mn) worst case, O(m + n) average case, O(n) best case
    int strStrRabinKarp(const string& text, const string& pattern, int inputBase = 128) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

        int i, j, patternHash(0), textHash(0), patternLenOut(0);

        // calculate hash value for pattern and text
        for (i = 0; i < n; i++) {
            patternHash = pattern[i] % inputBase;
            textHash = text[i] % inputBase;
        }

        // matching
        for (i = 0; i <= m - n; i++) {
            if (patternHash == textHash) {
                for (j = 0; j < n; j++)
                    if (text[i + j] != pattern[j])
                        break;

                if (j == n) return i;
            }

            if (i < m - n) {
                textHash = text[i + n] % inputBase;
                if (textHash < 0) textHash += inputBase;
            }
        }

        return -1;
    }

    // Boyer-Moore, O((m - n) * n) worst case (like brute force), O(m + n) average case, O(m/n) best case
    int strStr(const string& text, const string& pattern) {
        int m = text.size(), n = pattern.size();

        // be consistent with C/C++ strstr() and Java indexOf()
        if (!n) return 0;

        short badchar[255] = {-1};

        int i, s = 0;

        for (i = 0; i < n; i++) badchar[pattern[i]] = i;

        while (s <= m - n) {
            i = n - 1;

            while (i >= 0 && pattern[i] == text[s + i]) i--;

            if (i < 0) return s;

            s += max(1, i - badchar[text[s + i]]);
        }

        return -1;
    }

    // Other possible solution: Radix Sort
};