strstr.cpp

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