strstr(KMP实现)

KMP算法，关键在于求next数组，求next数组搞了好久都没搞懂，干脆记住算了。。。吧

//
// Created by jt on 2020/8/14.
//
#include <string>
using namespace std;

class Solution {
public:
    char *strStr(char *haystack, char *needle) {
        int size1 = strlen(haystack), size2 = strlen(needle);
        if (size2 == 0) return haystack;
        int next[size2], i = 0, j = 0;
        getNext(needle, next, size2);
        while(i < size1 && j < size2) {
            if (j == -1 || haystack[i] == needle[j]) {
                ++i;
                ++j;
            } else {
                j = next[j];
            }
        }
        if (j == size2) return haystack + i - j;
        else return nullptr;
    }

    void getNext(char *a, int *next, int size) {
        int i = 0, j = -1;      // i指向尾子串尾部，j指向头子串尾部
        next[0] = -1;
        while (i < size) {
            if (j == -1 || a[i] == a[j]) {
                if (a[++i] == a[++j]) next[i] = next[j];
                else next[i] = j;
            } else j = next[j];
        }
    }
};