用c语言实现数据结构串的KMP算法

KMP算法是一种字符串匹配算法，可以在一个主串中查找一个模式串是否出现。这里提供一个用C语言实现的KMP算法。

首先，需要定义一个函数`get_next`，用于计算模式串的next数组。next数组是一个长度为模式串长度的整型数组，表示当匹配失败时，模式串应该向右移动的位数。

void get_next(char* pattern, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(pattern)) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

接下来，定义一个函数`kmp`，用于在主串中查找模式串。函数的参数包括主串指针、主串长度、模式串指针、模式串长度和next数组。

int kmp(char* text, int text_len, char* pattern, int pattern_len, int* next) {
    int i = 0, j = 0;
    while (i < text_len && j < pattern_len) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == pattern_len) {
        return i - j;
    }
    else {
        return -1;
    }
}

下面是一个完整的示例代码：

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

void get_next(char* pattern, int* next) {
    int i = 0, j = -1;
    next[0] = -1;
    while (i < strlen(pattern)) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        }
        else {
            j = next[j];
        }
    }
}

int kmp(char* text, int text_len, char* pattern, int pattern_len, int* next) {
    int i = 0, j = 0;
    while (i < text_len && j < pattern_len) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        }
        else {
            j = next[j];
        }
    }
    if (j == pattern_len) {
        return i - j;
    }
    else {
        return -1;
    }
}

int main() {
    char text[] = "ABABABABCABAAB";
    char pattern[] = "ABABCABAA";
    int text_len = strlen(text);
    int pattern_len = strlen(pattern);
    int next[pattern_len];
    get_next(pattern, next);
    int pos = kmp(text, text_len, pattern, pattern_len, next);
    if (pos == -1) {
        printf("Pattern not found.\n");
    }
    else {
        printf("Pattern found at position %d.\n", pos);
    }
    return 0;
}

输出结果为：

Pattern found at position 6.

表示在主串中找到了模式串，并且位置为6。