KMP算法 c语言实现

KMP算法是一种字符串匹配算法，用于在一个文本串中查找一个模式串的出现位置。下面是一份用C语言实现的KMP算法代码：

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

void getNext(char* p, int* next) {
    int pLen = strlen(p);
    next[0] = -1;
    int k = -1, j = 0;
    while (j < pLen - 1) {
        if (k == -1 || p[j] == p[k]) {
            ++k;
            ++j;
            if (p[j] != p[k])
                next[j] = k;
            else
                next[j] = next[k];
        }
        else {
            k = next[k];
        }
    }
}

int kmp(char* s, char* p) {
    int sLen = strlen(s);
    int pLen = strlen(p);
    int* next = (int*)malloc(sizeof(int) * pLen);
    getNext(p, next);
    int i = 0, j = 0;
    while (i < sLen && j < pLen) {
        if (j == -1 || s[i] == p[j]) {
            ++i;
            ++j;
        }
        else {
            j = next[j];
        }
    }
    free(next);
    if (j == pLen) {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    char s[] = "hello world";
    char p[] = "world";
    int pos = kmp(s, p);
    if (pos == -1) {
        printf("Pattern not found\n");
    }
    else {
        printf("Pattern found at position %d\n", pos);
    }
    return 0;
}

在这份代码中，getNext函数用于计算模式串p的next数组，kmp函数用于在文本串s中查找模式串p的出现位置。其中，next数组用于优化匹配过程，它记录了当匹配失败时模式串应该跳到哪个位置继续匹配。具体的实现可以参考代码注释