Leetcode之算法专题《Implement strStr()》(By Kmp)

题目内容如下（链接：https://leetcode.com/problems/implement-strstr/description/）

中文说明：用kmp算法实现strstr函数

Implement strStr().

Return the index of the first occurrence of needle in haystack, or -1 if needle is not part of haystack.

Example 1:

Input: haystack = "hello", needle = "ll"
Output: 2

Example 2:

Input: haystack = "aaaaa", needle = "bba"
Output: -1

class Solution {
public:
    int strStr(string haystack, string needle) {
        int iNeedleSize = needle.size();
        if(iNeedleSize == 0) return 0;
        int* next = new int[iNeedleSize];
        get_next(next, needle, iNeedleSize);
        int i=0;
        int j=0;
        int iHayStackSize = haystack.size();
        while(i < iHayStackSize && j < iNeedleSize){
            if(j == -1 || haystack[i] == needle[j]){
                ++i;
                ++j;
            }else{
                j = next[j];
            }
        }
        delete[] next;
        if(j == iNeedleSize){
            return i-j;
        }
        return -1;
    }
    void get_next(int* next, const string& p, const int& len){
        next[0] = -1;
        int j = 0;
        int k = -1;
        while(j<len-1){
            if(k == -1 || p[j] == p[k]){
                if(p[++j] == p[++k]){
                    next[j] = next[k];
                }else{
                    next[j] = k;
                }
            }else{
                k = next[k];
            }
        }
    }
    
};

运行结果：