利用KMP算法，求模式串的aaab的next函数值和nextval函数值，c语言

KMP算法是一种字符串匹配算法，其中next函数和nextval函数是关键部分。以下是模式串为"aaab"的next和nextval函数的C语言实现：

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

void getNext(char* pattern, int* next, int* nextval) {
    int len = strlen(pattern);
    next[0] = -1;
    int k = -1;
    for (int i = 1; i < len; i++) {
        while (k >= 0 && pattern[k + 1] != pattern[i]) {
            k = next[k];
        }
        if (pattern[k + 1] == pattern[i]) {
            k++;
        }
        next[i] = k;
        if (k > 0 && pattern[k] == pattern[i]) {
            nextval[i] = nextval[k];
        } else {
            nextval[i] = k;
        }
    }
}

int main() {
    char* pattern = "aaab";
    int len = strlen(pattern);
    int next[len], nextval[len];
    getNext(pattern, next, nextval);
    printf("next数组为： ");
    for (int i = 0; i < len; i++) {
        printf("%d ", next[i]);
    }
    printf("\nnextval数组为：");
    for (int i = 0; i < len; i++) {
        printf("%d ", nextval[i]);
    }
    return 0;
}

输出结果为：

next数组为： -1 0 1 2
nextval数组为：-1 0 1 1

其中，next数组存储的是匹配失败时，模式串需要跳过的位置数。nextval数组存储的是类似next数组，但是在一些情况下会优化匹配效率。