用c++写一个KMP算法

### 回答1：
KMP算法是一种字符串匹配算法，可以快速在文本串中找到模式串的出现位置。

下面是一个用C语言实现的KMP算法的示例代码：

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

// 计算 next 数组
void get_next(char *p, int *next) {
    int p_len = strlen(p);
    next[0] = -1;
    int k = -1;
    int j = 0;
    while (j < p_len - 1) {
        // p[k] 表示前缀，p[j] 表示后缀
        if (k == -1 || p[k] == p[j]) {
            ++k;
            ++j;
            next[j] = k;
        } else {
            k = next[k];
        }
    }
}

// KMP 匹配字符串
int kmp_match(char *s, char *p) {
    int s_len = strlen(s);
    int p_len = strlen(p);
    int *next = (int*)malloc(sizeof(int) * p_len);
    get_next(p, next);
    int i = 0;
    int j = 0;
    while (i < s_len && j < p_len) {
        // ①如果 j = -1，或者当前字符匹配成功（即 S[i] == P[j]），都令 i++，j++
        if (j == -1 || s[i] == p[j]) {
            i++;
            j++;
        } else {
            // ②如果 j != -1，且当前字符匹配失败（即 S[i] != P[j]），则令 i 不变，j = next[j]
            // next[j] 即为 j 所对应的 next 值
            j = next[j];
        }
    }
    free(next);
    if (j == p_len) {
        // 匹配成功
        return i - j;
    } else {
        // 匹配失败
        return -1;
    }
}

int main() {
    char *s = "BBC ABCDAB ABCDABCDABDE";
    char *p = "ABCDABD";
    int result = kmp_match(  

### 回答2：
KMP算法（Knuth-Morris-Pratt算法）是一种用于字符串匹配的高效算法。其核心思想是利用已经匹配过的部分信息，避免对已经比较过的元素进行重复比较，从而提高匹配的效率。

以下是用C语言实现KMP算法的示例代码：

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

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

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 KMPSearch(char* pattern, char* text) {
int m = strlen(pattern);
int n = strlen(text);

int lps[m];

computeLPSArray(pattern, lps);

int i = 0;
int j = 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 = i + 1;
}
}
}
}

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

KMPSearch(pattern, text);

return 0;
}

这段代码中，`KMPSearch`函数用来实现KMP算法的主要逻辑，其中`computeLPSArray`函数用于计算pattern字符串的最长公共前后缀长度。

以上就是使用C语言编写KMP算法的示例代码，通过KMP算法可以高效地在一个文本字符串中搜索多个模式字符串。  

### 回答3：
KMP算法是一种字符串匹配算法，用于在一个较长的字符串中查找一个较短的字符串是否存在。下面是使用C语言编写的KMP算法的示例代码：

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

// 计算next数组
void computeNextArray(char* pattern, int* next) {
int patternLen = strlen(pattern);
next[0] = -1;
int i = 0, j = -1;
while (i < patternLen) {
if (j == -1 || pattern[i] == pattern[j]) {
i++;
j++;
next[i] = j;
} else {
j = next[j];
}
}
}

// KMP算法
int KMPSearch(char* text, char* pattern) {
int textLen = strlen(text);
int patternLen = strlen(pattern);

int* next = (int*)malloc((patternLen + 1) * sizeof(int));
computeNextArray(pattern, next);

int i = 0, j = 0;
while (i < textLen) {
if (j == -1 || text[i] == pattern[j]) {
i++;
j++;
} else {
j = next[j];
}

if (j == patternLen) {
free(next);
return i - j; // 返回匹配到的字符串在文本中的起始位置
}
}

free(next);
return -1; // 没有找到匹配的字符串
}

int main() {
char text[100], pattern[100];
printf("请输入文本字符串：");
scanf("%s", text);
printf("请输入要查找的字符串：");
scanf("%s", pattern);

int position = KMPSearch(text, pattern);
if (position == -1) {
printf("在文本字符串中未找到匹配的字符串。\n");
} else {
printf("在文本字符串中找到了匹配的字符串，起始位置：%d\n", position);
}

return 0;
}

以上是一个简单的KMP算法的实现，通过在算法中利用next数组来避免不必要的模式串回溯。算法首先计算出模式串的next数组，然后在文本串中进行匹配。最终输出匹配的起始位置或者未找到匹配的提示信息。