c++ kmp算法实现

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个主串中查找一个模式串的出现位置。下面是KMP算法的实现示例（使用C语言）：

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

void computeLPSArray(char* pattern, int pattern_length, int* lps) {
    int len = 0;
    lps[0] = 0; // lps[0]总是0

    int i = 1;
    while (i < pattern_length) {
        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 text_length = strlen(text);
    int pattern_length = strlen(pattern);

    // 创建并初始化lps数组
    int* lps = (int*)malloc(sizeof(int) * pattern_length);
    computeLPSArray(pattern, pattern_length, lps);

    int i = 0; // text中的索引
    int j = 0; // pattern中的索引
    while (i < text_length) {
        if (pattern[j] == text[i]) {
            j++;
            i++;
        }

        if (j == pattern_length) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < text_length && pattern[j] != text[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i++;
            }
        }
    }

    free(lps);
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    KMP(text, pattern);
    return 0;
}

这是一个简单的KMP算法实现，可以在给定的文本中查找指定的模式串。当找到匹配时，会输出模式串在文本中的起始索引。

注意，在使用这段代码时，需要包含`<stdio.h>`和`<string.h>`头文件，并在编译时链接数学库（例如，使用`-lm`选项）。

希望这个示例能对你有所帮助！如果还有其他问题，请随时提问。