28. Implement strStr() (Easy)

Implement strStr().

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

Solution 1: Brute Force

int strStr(string haystack, string needle) {
    int len = needle.size();
    int n = haystack.size() - len;
    for (int i = 0; i <= n; ++i) {
        int j = 0;
        for (; j < len; ++j) {
            if (haystack[i+j] != needle[j]) break;
        }
        if (j == len) return i;
    }
    return -1;
}

Solution 2: KMP

int strStr(string haystack, string needle) {
    // build pattern
    if (needle.size() == 0) return 0;
    int j = 0, n = needle.size(), m = haystack.size();
    int P[n]; P[0] = 0;
    for (int i = 1; i < n; ++i) {
        while (j > 0 && needle[j] != needle[i]) j = P[j-1];
        if (needle[j] == needle[i]) ++j;
        P[i] = j;
    }

    j = 0;
    for (int i = 0; i < m; ++i) {
        while (j > 0 && needle[j] != haystack[i]) j = P[j-1];
        if (needle[j] == haystack[i]) {
            if (++j == n) return i-n+1;
        }
    }
    return -1;
}