std::vector<int> build_next(const std::string& pattern) {
    int n = pattern.length();
    std::vector<int> next(n, 0);
    int j = -1;
    next[0] = j;

    for (int i = 1; i < n; i++) {
        // 当前缀和后缀不同，向前回溯
        while (j >= 0 && pattern[i] != pattern[j + 1]) {
            j = next[j];
        }

        // 当前缀和后缀相同
        if (pattern[i] == pattern[j + 1]) {
            j++;
        }

        next[i] = j;
    }

    return next;
}

std::vector<int> kmp_search(const std::string& text, const std::string& pattern) {
    std::vector<int> positions; // 存储匹配的起始位置
    std::vector<int> next = build_next(pattern);
    int j = -1;

    for (int i = 0; i < text.length(); i++) {
        // 当前字符不匹配，根据next数组回溯模式字符串的指针
        while (j >= 0 && text[i] != pattern[j + 1]) {
            j = next[j];
        }

        // 当前字符匹配
        if (text[i] == pattern[j + 1]) {
            j++;
        }

        // 完全匹配模式字符串
        if (j == pattern.length() - 1) {
            positions.push_back(i - j);
            j = next[j]; // 继续搜索下一个匹配
        }
    }

    return positions;
}

class Solution {
public:
    //构造 next 数组
    void getNext(int* next, const string& s){
    int j = -1;
    next[0] = j;
    for(int i = 1; i < s.size(); i++) {
        while (j >= 0 && s[i] != s[j + 1]) {
            j = next[j]; 
        }
        if (s[i] == s[j + 1]) { 
            j++;
        }
        next[i] = j; 
    }
}
    int strStr(string haystack, string needle) {
        //KMP算法
         if (needle.size() == 0) {
            return 0;
        }
        int next[needle.size()];
        getNext(next, needle);
        int j = -1; // // 因为next数组里记录的起始位置为-1
        for (int i = 0; i < haystack.size(); i++) { // 注意i就从0开始
            while(j >= 0 && haystack[i] != needle[j + 1]) { // 不匹配
                j = next[j]; // j 寻找之前匹配的位置
            }
            if (haystack[i] == needle[j + 1]) { // 匹配，j和i同时向后移动
                j++; // i的增加在for循环里
            }
            if (j == (needle.size() - 1) ) { // 文本串s里出现了模式串t
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};