[LeetCode 28] Implement strStr()

Implement strStr().

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

Diffculty
Easy

Similar Problems
[LeetCode ] Shortest Palindrome Hard

Analysis

class Solution { public: int strStr(string haystack, string needle) { for (int i = 0;; i++) { for (int j = 0;; j++) { if (j == needle.length()) return i; if (i + j == haystack.length()) return -1; if (needle[j] != haystack[i + j]) break; } } } };

// optimized kmp class Solution { public: void getNext(vector &next, string &needle) { int i = 0, j = -1; next[i] = j; while (i < needle.length() - 1) { while (j != -1 && needle[i] != needle[j]) j = next[j]; ++i; ++j; //特殊情况，这里即为优化之处。考虑下AAAAB, 防止4个A形成0123在匹配时多次迭代。 if (needle[i] == needle[j]) next[i] = next[j]; else next[i] = j; } }

int strStr(string haystack, string needle) {
    if (haystack.empty()) return needle.empty() ? 0 : -1;
    if (needle.empty()) return 0;
    vector<int> next(needle.length() + 1);
    getNext(next, needle);
    int i = 0, j = 0;
    while (i != haystack.length()) {
        while (j != -1 && haystack[i] != needle[j]) j = next[j];
        ++i; ++j;
        if (j == needle.length()) return i - j;
    }
    return -1;
}

};