使用C语言编写KMP算法

KMP算法是一种字符串匹配算法，用于在一个长度为N的文本字符串中查找一个长度为M的模式字符串的出现位置。它的核心思想是利用已匹配的字符串信息来减少不必要的比较次数。

下面是使用C语言实现KMP算法的代码：

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

// 计算模式字符串的next数组
void getNext(char *pat, int *next, int len) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < len - 1) {
        if (j == -1 || pat[i] == pat[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// 使用KMP算法查找模式字符串在文本字符串中的位置
int kmp(char *txt, char *pat) {
    int n = strlen(txt);
    int m = strlen(pat);
    int i = 0, j = 0;
    int *next = (int *)malloc(sizeof(int) * m);

    getNext(pat, next, m);

    while (i < n && j < m) {
        if (j == -1 || txt[i] == pat[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }

    if (j == m) {
        return i - j;
    } else {
        return -1;
    }
}

int main() {
    char txt[100], pat[100];

    printf("请输入文本字符串：");
    scanf("%s", txt);

    printf("请输入模式字符串：");
    scanf("%s", pat);

    int pos = kmp(txt, pat);

    if (pos == -1) {
        printf("在文本字符串中没有找到模式字符串！\n");
    } else {
        printf("模式字符串在文本字符串中的位置是：%d\n", pos+1);
    }

    return 0;
}

在实现过程中，我们需要先计算出模式字符串的next数组，然后使用双指针i和j在文本字符串和模式字符串上进行扫描，当匹配不成功时，利用next数组跳过部分已经匹配过的字符，以减少比较次数。如果最终j的值等于模式字符串的长度，则说明找到了一次匹配，返回i-j即为该匹配的起始位置。如果最终j的值不等于模式字符串的长度，则说明匹配失败。