kmp算法next数组的求法，用两个for循环一个while循环，代码示例，用c++

KMP算法（Knuth-Morris-Pratt 算法）是一种用于字符串匹配的高效算法，它通过预处理模式串来减少不必要的字符比较。在KMP算法中，`next` 数组存储了模式串中每个位置前缀最长公共前后缀的长度信息。

首先，我们需要创建一个`next`数组，其初始值通常为0。对于每个索引`i`（从1开始），如果`pattern[i]`等于`text[prefix_length + i]`（也就是当前字符和之前最长公共前缀的下一个字符相等），那么`next[i]`就是`prefix_length + 1`；否则，我们沿着`next`数组查找前缀公共部分，即寻找`next[j]`（使得`pattern[j] == pattern[i]`并且`j < prefix_length`)，然后将`next[i]`设为`j + 1`。如果找不到这样的`j`，说明从头开始找，将`next[i]`设置为0。

下面是一个使用 C++ 实现 KMP 算法生成 `next` 数组的简单示例：

#include <vector>
#include <string>

std::vector<int> getNext(const std::string& pattern) {
    int prefix_length = 0;
    std::vector<int> next(pattern.size(), 0);
    
    for (int i = 1; i < pattern.size(); ++i) {
        while (prefix_length > 0 && pattern[prefix_length] != pattern[i]) {
            prefix_length = next[prefix_length - 1];
        }
        
        if (pattern[prefix_length] == pattern[i]) {
            ++prefix_length;
        }
        
        next[i] = prefix_length;
    }
    
    return next;
}

// 主函数里如何使用 next 数组进行字符串搜索
int main() {
    std::string text = "ABABDABACDABABC";
    std::string pattern = "ABAC";
    std::vector<int> next = getNext(pattern);

    // 使用 next 数组进行匹配
    for (size_t i = 0; i < text.size(); ++i) {
        if (i + pattern.size() <= text.size()) {
            int j = 0;
            while (j < pattern.size() && i + j < text.size() && text[i + j] == pattern[j]) {
                j++;
            }
            
            if (j == pattern.size()) {
                // 找到匹配的位置
                std::cout << "Pattern found at index " << i << std::endl;
            } else {
                j = next[j - 1]; // 如果没找到直接匹配，尝试跳过
            }
        }
    }

    return 0;
}