用c语言实现KMP算法

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

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

void computeLPSArray(char* pattern, int* lps) {
    int len = 0;
    int i = 1;
    int patternLen = strlen(pattern);

    while (i < patternLen) {
        if (pattern[i] == pattern[len]) {
            len++;
            lps[i] = len;
            i++;
        }
        else {
            if (len != 0) {
                len = lps[len - 1];
            }
            else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void KMP(char* text, char* pattern) {
    int textLen = strlen(text);
    int patternLen = strlen(pattern);

    int* lps = (int*)malloc(sizeof(int) * patternLen);
    computeLPSArray(pattern, lps);

    int i = 0; // text中的索引
    int j = 0; // pattern中的索引

    while (i < textLen) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }

        if (j == patternLen) {
            printf("在位置 %d 找到匹配\n", i - j);
            j = lps[j - 1];
        }

        // 不匹配的情况
        else if (i < textLen && text[i] != pattern[j]) {
            if (j != 0) {
                j = lps[j - 1];
            }
            else {
                i++;
            }
        }
    }

    free(lps);
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";

    KMP(text, pattern);

    return 0;
}

这是一个简单的使用C语言实现的KMP算法示例。你可以将待匹配的文本串和模式串分别传递给`KMP`函数，它会打印出模式串在文本串中的出现位置。注意，该示例只能找到第一个匹配的位置，如果你需要找到所有的匹配位置，可以稍作修改。