题目描述

原题链接：28. 找出字符串中第一个匹配项的下标

KMP理论及实现

41、【匹配算法】KMP字符串匹配算法（C/C++版）

next不减方式构造

class Solution {
public:
    void getNext(int next[], string &needle, int m) {
        next[0] = 0;
        for(int i = 1, j = 0; i < m; i++) {
            while(j > 0 && needle[i] != needle[j])    j = next[j - 1];
            if(needle[i] == needle[j])    j++;
            next[i] = j;
        }
    }  
    int strStr(string haystack, string needle) {
        if(needle.size() == 0 || haystack.size() == 0)      return -1;
        int n = haystack.size(), m = needle.size();
        int next[m];
        getNext(next, needle, m);
        for(int i = 0, j = 0; i < n; i++) {
            while(j > 0 && haystack[i] != needle[j])    j = next[j - 1];
            if(haystack[i] == needle[j])    j++;
            if(j == m) {
                return i - j + 1;       // 因为j的范围为0~m-1，因此需要返回的是i - (j - 1)
            }
        }
        return -1;
    }
};

时间复杂度 $O(n+m)$
空间复杂度 $(m)$

参考文章：28. 实现 strStr()