2、有目标串s=“bbcgabcdabgabcdabcdabde”和模式串t=“abcdabd”。（1）用KMP算法进行模式匹配，共经过几次比较？ 用c语言写

KMP算法（Knuth-Morris-Pratt算法）是一种用于字符串匹配的高效算法，它利用了已知模式串的信息来避免不必要的字符比较。对于给定的目标串s和模式串t，KMP算法的主要步骤包括：

1. 构建失配函数next[]：这个函数表示当在模式串中从某个位置i开始匹配时，如果遇到前缀不匹配，则移动到下标next[i]的位置继续尝试。失配函数帮助我们在遇到错误的情况下跳过多余的比较。

2. 比较字符：使用失配函数next[], 从目标串的第一个字符开始，逐个与模式串中的字符进行匹配。如果相等，则继续；如果不等，则根据next[]调整模式串的位置。

现在，我们先计算失配函数next[]：

s = "bbcgabcdabgabcdabcdabde"
t = "abcdabd"

构建next数组的过程：
- next[0] = -1 (初始值)
- next[1] = -1 (对于长度为1的模式)
- next[2] = 0 (因为"ac"是"abc"的一个前缀)
- next[3] = 1 (因为"bcd"是"abcd"的一个前缀)
- ... (以此类推)

最终，对于模式串t="abcdabd"，失配函数可能是：{-1, -1, 0, 1, 2}

接下来是实际的KMP匹配过程。假设我们从目标串的第一个字符开始比较：

- 第一步：s[0] == t[0], 没有跳过，计数器k = 1
- 第二步：s[1] != t[1], 不匹配，但因为next[1] = -1，我们直接检查下一个位置s[0]
- s[0] == t[0], 匹配，k++
- ...
- 直到最后找到一个完整的匹配或遍历完目标串。

由于模式串"abcdabd"出现了两次，第一次完整匹配后会再次从目标串的第二个"abcd"处开始，直到找到第二次匹配结束。所以，总共会有5次完整的匹配（每次都是"abcd"），加上最后一次"abd"的不完全匹配，总共有6次比较。

下面是简单的C语言实现（假设next[]已经预处理好）：

#include <stdio.h>

int main() {
    char s[] = "bbcgabcdabgabcdabcdabde";
    char t[] = "abcdabd";
    int len_s = sizeof(s) - 1;
    int len_t = sizeof(t) - 1;

    int k = 0; // 记录模式匹配的指针
    int j = 0; // 记录目标串的指针

    while (j < len_s && k < len_t) {
        if (s[j] == t[k]) {
            k++;
        } else if (k > 0) {
            k = next[k - 1];
        } else {
            j++;
        }
        // 检查是否完成了一次完整的匹配
        if (k == len_t) {
            printf("找到一次匹配\n");
            k = 0;
        }
    }

    // 如果还有剩余的未匹配部分，说明没有找到完整匹配
    if (k > 0) {
        printf("模式串未在目标串中找到\n");
    }

    return 0;
}