学步园

Question：

Implement strStr().

Returns a pointer to the first occurrence of needle in haystack, or null if needle is not part of haystack.

Anwser 1：  O(n*m）

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int haylen = strlen(haystack);
        int needlen = strlen(needle);
        
        for(int i = 0; i <= haylen - needlen; i++){
            char *p = haystack + i;
            char *q = needle;
            while(*q != '\0'){
                if(*p != *q){
                    break;
                } else {
                    p++;
                    q++;
                }
            }
            
            if(*q == '\0'){
                return haystack + i;
            }
        }
        
        return NULL;
    }
};

Anwser 2：  O(n + m) KMP

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        // Start typing your C/C++ solution below
        // DO NOT write int main() function
        int haylen = strlen(haystack);
        int needlen = strlen(needle);
        int* fail = new int[needlen];
        memset(fail, -1, needlen * sizeof(int));    // strlen(fail)
        
        int i, j, k;
        for (i = 1; i < needlen; ++i) {
            for (k = fail[i-1]; k >= 0 && needle[i] != needle[k+1]; k = fail[k]);
            if (needle[k+1] == needle[i])
                fail[i] = k + 1;
        }
        
        i = j = 0;
      
       while(i < haylen && j < needlen)      // while(haystack[i] && needle[j])
        {
            if (haystack[i] == needle[j])
            {
                ++i;
                ++j;
            }
            else if(j == 0) ++i;
            else j = fail[j-1] + 1;
        }
        
        delete fail;
        
        /*
        if (needle[j]) {
            return NULL;
        }  else {
            return haystack + i - j;
        }*/
        if(j == needlen){
            return haystack + i - j;
        } else {
            return NULL;
        }
    }
};

参考推荐：

KMP字符串匹配算法