C语言写程序，已知主串s='ADBADABBAABADABBADADA',模式串pat='ADABBADADA',写出模式串的nextval函数值，并

在C语言中，要编写一个`nextval`函数来计算模式串`pat`的Next Fit算法（也称为KMP算法），用于在一个较长的主串`s`中查找该模式串的所有匹配位置。首先，我们需要创建一个部分匹配表（Partial Match Table，简称PMT或也称为失配指针数组）。这个数组存储了模式串中每个前缀与自身剩余部分最长公共前后缀的长度。

给定主串s = 'ADBADABBAABADABBADADA' 和模式串pat = 'ADABBADADA'，我们先创建PMT:

1. 初始化PMT数组:
- pat[0] = 0 (空字符串的LCP为0)
- i = 1; j = 0;
- while i < strlen(pat) {
if pat[i] == pat[j]:
j++;
PMT[i] = j;
i++;
else if j != 0: // 如果当前字符不匹配，回溯到上一次相等的位置
j = PMT[j - 1];
else: // 如果j已经是最小，i继续直到找到下一个不匹配的位置
PMT[i] = 0;
i++;
}

最终得到的PMT数组将是：

0, 0, 1, 2, 0, 4, 6, 7, 8, 9

然后，对于主串`s`中的每一个字符，我们可以从头开始比较，如果遇到匹配就更新索引，如果不匹配则跳过`PMT[i]`位数继续。这样就可以找出所有模式串在主串中的起始位置。

接下来，我会给出`nextval`函数的大致实现，不过请注意这只是一个简化版本，实际应用中还需要处理边界条件、输入检查等细节：

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

int nextVal(char* pat, char* s, int i, int* PMT) {
    if (i >= strlen(s)) return -1; // 搜索结束，未找到匹配

    if (pat[i] == s[i]) { // 相同字符，向前移动
        return i + 1;
    } else if (PMT[i] > 0) { // 模式串中有匹配部分，使用PMT跳跃
        return nextVal(pat, s, i + PMT[i], PMT);
    } else { // 没有匹配，直接继续搜索主串
        return nextVal(pat, s, i + 1, PMT);
    }
}

// 示例主函数
int main() {
    char s[] = "ADBADABBAABADABBADADA";
    char pat[] = "ADABBADADA";
    int len_s = strlen(s);
    int len_pat = strlen(pat);
    int PMT[len_pat];

    // 初始化PMT
    buildPMT(len_pat, pat, PMT);

    for (int i = 0; i <= len_s - len_pat; i++) {
        int match_pos = nextVal(pat, s, i, PMT);
        if (match_pos != -1) printf("Match found at index %d\n", i);
    }

    return 0;
}