28. Implement strStr()

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

Clarification:

What should we return when needle is an empty string? This is a great question to ask during an interview.

For the purpose of this problem, we will return 0 when needle is an empty string. This is consistent to C's strstr() and Java's indexOf().

int strStr(string haystack, string needle) { // time: O(m * n); space: O(1)
    int m = haystack.size(), n = needle.size();
    if (m < n) return -1;
    if (n == 0) return 0;
    int i = 0, j = 0;
    for (; i <= m - n; ++i) {
        if (haystack[i] == needle[j]) {
            while (i + j < m && haystack[i + j] == needle[j]) ++j;
            if (j == n) break;
            else j = 0;
        }
    }
    return j == n ? i : -1;
}

int strStr(string haystack, string needle) { // time: O(m * n); space: O(1) 
    int m = haystack.size(), n = needle.size();
    for (int i = 0; i <= m - n; ++i) {
        for (int j = 0; j <= n; ++j) {
            if (j == n) return i;
            // if (i + j == m) return -1;
            if (needle[j] != haystack[i + j]) break;
        }
    }
    return -1;
}

Rabin-Karp演算法可以達到線性的時間複雜度。

// Rabin-Karp Algorithm (Modular Hash Function)
int strStr(string haystack, string needle) { // time: O(m + n); space: O(1)
    int m = haystack.length(), n = needle.length();
    if (n == 0) return 0;
    int R = 31, Q = 997, RN = 1;
    for (int i = 0; i < n; ++i) RN = (RN * R) % Q;
    int targetHash = 0;
    for (int i = 0; i < n; ++i) targetHash = (targetHash * R + needle[i]) % Q;
    int sourceHash = 0;
    for (int i = 0; i < m; ++i) {
        sourceHash = (sourceHash * R + haystack[i]) % Q;
        if (i < n - 1) continue;
        if (i >= n) {
            sourceHash = sourceHash - (haystack[i - n] * RN) % Q;
            if (sourceHash < 0) sourceHash += Q;
        }
        if (sourceHash == targetHash) {
            if (haystack.substr(i - n + 1, n) == needle) {
                return i - n + 1;
            }
        }
    }
    return -1;
}