1.描述

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

Subscribe to see which companies asked this question.

2.方法一

2.1分析

暴力匹配

2.2代碼

int strStr(char* haystack, char* needle) {
    if (NULL == haystack || NULL == needle) return -1;
    unsigned int l1 = strlen(haystack);
    unsigned int l2 = strlen(needle);
    if (0 >= l2) return 0;
    if (0 >= l1) return -1;
    
    unsigned int i = 0, j = 0;
    while (i < l1 && j < l2) {
        if (haystack[i] == needle[j]) {
            ++i;
            ++j;
        } else {
            i = i - (j-1);
            j = 0;
        }
    }
    return j >= l2 ? i - l2 : -1;
}

3.方法二

3.1 分析

KMP 算法