Day 53, 28, Implement strStr()

Implement strStr()
Implement strStr().
Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.
------------------------------------------------- 
KMP, O(n),

class Solution {
public:
    vector<int> computePrefixTable(string pattern) {
        int m = pattern.length();
        vector<int> table(m,0);
        int matchedLength = 0;
        
        for (int i = 1; i < m; i++) {
            // until find the next char at matchedLength is equal to char at i
            // or matchedLength is zero
            while (matchedLength > 0 && pattern[matchedLength] != pattern[i]) {
                matchedLength = table[matchedLength - 1];
            }
            if (pattern[matchedLength] == pattern[i]) {
                matchedLength++;
            }
            table[i] = matchedLength;
        }
        
        return table;
    }
    
    int KMP(string source, string pattern) {
        int n = source.length();
        int m = pattern.length();
        vector<int> table = computePrefixTable(pattern);
        int matchedLength = 0;
        
        for (int i = 0; i < n; i++) {
            while (matchedLength > 0 && pattern[matchedLength] != source[i]) {
                matchedLength = table[matchedLength - 1];
            }
            
            if (pattern[matchedLength] == source[i]) {
                matchedLength++;
            }
            if (matchedLength == m) {
                return i - m + 1;
            }
        }
        
        return -1;
    }

    int strStr(string haystack, string needle) {
        if (needle == "") return 0;
        if (haystack == "") return -1;
        return KMP(haystack,needle);
    }
};

Solution #2 O(m*n), improved brute force

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // IMPORTANT: Please reset any member data you declared, as
        // the same Solution instance will be reused for each test case.
        if (*needle == NULL) return haystack;
        if (!*haystack) return NULL;
        char* adv = haystack;
        char* temp = needle;
        while (*++temp) {
            adv++;
        }
        
        while (*adv != NULL) {
            char* itr1 = haystack;
            char* itr2 = needle;
            while (*itr1 && *itr2 && *itr1 == *itr2) {
                itr1++;
                itr2++;
            }
            if (!*itr2) return haystack;
            haystack++;
            adv++;
        }
        return NULL;
    }
};