用c语言写一个kmp算法中求解next数组的函数

在C语言中，KMP（Knuth-Morris-Pratt）算法用于字符串匹配，其中`next`数组是一个关键组成部分，它存储了模式串中每个位置之后的最长前缀和当前字符相同的长度。以下是编写计算`next`数组的函数的一个简单示例：

#include <stdio.h>
#include <string.h>

// 定义next数组大小
#define MAX_SIZE 1000

void computeNext(char pattern[], int next[]) {
    int len = strlen(pattern);
    next[0] = -1; // 根据KMP规则，如果模式的第一个字符是自己，next[0] = 0
    int j = -1;
    
    for (int i = 1; i < len; ++i) {
        while (j != -1 && pattern[i] != pattern[j + 1]) { // 如果当前位置的字符不等于上次失败的位置的下一个字符
            j = next[j]; // 跳到上次成功的next值
        }
        
        if (pattern[i] == pattern[j + 1]) { // 如果相等，则向右移动
            j++;
        }
        
        next[i] = j; // 记录当前位置的next值
    }
}

// 示例如何使用
int main() {
    char pattern[] = "ababcab"; // 模式串
    int next[MAX_SIZE];
    computeNext(pattern, next);
    
    printf("Next array: ");
    for (int i = 0; i < strlen(pattern); ++i) {
        printf("%d ", next[i]);
    }
    
    return 0;
}

在这个函数中，我们首先初始化`next[0]`为-1，然后从第二个字符开始遍历模式串，每次遇到不匹配的情况就回溯到上一次成功的`next`值，直到找到匹配的字符为止。这个过程构建了`next`数组。