用C++代码写一个KMP

### 回答1：
好的，以下是KMP算法的C语言实现：

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

void compute_lps(char* pat, int M, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    while (i < M) {
        if (pat[i] == pat[len]) {
            len++;
            lps[i] = len;
            i++;
        } else {
            if (len != 0) {
                len = lps[len - 1];
            } else {
                lps[i] = 0;
                i++;
            }
        }
    }
}

void kmp_search(char* pat, char* txt) {
    int M = strlen(pat);
    int N = strlen(txt);

    int lps[M];
    compute_lps(pat, M, lps);

    int i = 0;
    int j = 0;
    while (i < N) {
        if (pat[j] == txt[i]) {
            j++;
            i++;
        }

        if (j == M) {
            printf("Pattern found at index %d\n", i - j);
            j = lps[j - 1];
        } else if (i < N && pat[j] != txt[i]) {
            if (j != 0) {
                j = lps[j - 1];
            } else {
                i = i + 1;
            }
        }
    }
}

int main() {
    char txt[] = "ABABDABACDABABCABAB";
    char pat[] = "ABABCABAB";
    kmp_search(pat, txt);
    return 0;
}

以上就是使用C语言实现KMP算法的代码，它可以在给定的文本中查找一个模式串的出现位置。

### 回答2：
KMP算法是一种高效的字符串匹配算法，用于解决字符串匹配的问题。下面是用C语言编写KMP算法的代码示例：

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

void computeLPSArray(char* pattern, int M, int* lps) {
    int len = 0;
    int i = 1;
    lps[0] = 0;

    while (i < M) {
        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* pattern, char* text) {
    int M = strlen(pattern);
    int N = strlen(text);

    int* lps = (int*)malloc(sizeof(int) * M);
    int j = 0;

    computeLPSArray(pattern, M, lps);

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

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

    free(lps);
}

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

    KMP(pattern, text);
    return 0;
}

以上是一个基于C语言的KMP算法示例。该代码中的`computeLPSArray`函数用于计算匹配模式的最长公共前缀和后缀（Longest Prefix that is also Suffix），`KMP`函数则是实现了KMP算法的主体逻辑。在`main`函数中，我们可以通过调用`KMP`函数进行字符串匹配，输出匹配成功的子串在原始字符串中的位置。

### 回答3：
KMP算法是一种字符串匹配算法，用于在一个（主）字符串中查找一个（模式）字符串的出现位置。下面是使用C代码实现KMP算法的示例：

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

void buildLPSArray(char* pattern, int patternLen, int* lps) {
    int len = 0;
    lps[0] = 0;
    int i = 1;
    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[patternLen];
    buildLPSArray(pattern, patternLen, lps);

    int i = 0;  // 文本字符串中的当前位置
    int j = 0;  // 模式字符串中的当前位置
    while (i < textLen) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == patternLen) {
            printf("模式出现的位置: %d\n", i - j);
            j = lps[j - 1];
        }
        else if (i < textLen && pattern[j] != text[i]) {
            if (j != 0)
                j = lps[j - 1];
            else
                i++;
        }
    }
}

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

这段代码实现了一个简单的KMP算法，用来在`text`字符串中查找`pattern`字符串的出现位置。它使用了两个函数：`buildLPSArray`用于构建`pattern`字符串的最长公共前缀和后缀数组，`KMP`函数则用于实际的匹配操作。在`main`函数中，我们可以自定义`text`和`pattern`字符串来进行测试。运行程序后，将会输出模式出现的位置：`模式出现的位置: 10`。