请用c加加给我写一段kmp的代码

### 回答1：

#include <stdio.h>
int KMP(char *s, char *p) {
int s_len = strlen(s);
int p_len = strlen(p);
int i = 0, j = 0;
int next[p_len];
get_next(p, p_len, next);
while (i < s_len && j < p_len) {
if (j == -1 || s[i] == p[j]) {
i++;
j++;
}
else {
j = next[j];
}
}
if (j == p_len)
return i - j;
else
return -1;
}void get_next(char *p, int p_len, int next[]) {
int j = 0, k = -1;
next[0] = -1;
while (j < p_len - 1) {
if (k == -1 || p[j] == p[k]) {
j++;
k++;
next[j] = k;
}
else
k = next[k];
}
}

### 回答2：
KMP算法是一种用于字符串匹配的常用算法，它的核心思想是通过利用已匹配过的前缀信息，避免不必要的比较，提高匹配效率。下面是使用C++编写的KMP算法代码。

#include <iostream>
#include <vector>
using namespace std;

vector<int> getNext(const string& pattern) {
    int n = pattern.length();
    vector<int> next(n, 0);
    int i = 1, len = 0;
    
    while (i < n) {
        if (pattern[i] == pattern[len]) {
            len++;
            next[i] = len;
            i++;
        }
        else {
            if (len > 0) {
                len = next[len - 1];
            }
            else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

int kmp(const string& text, const string& pattern) {
    int m = text.length();
    int n = pattern.length();
    vector<int> next = getNext(pattern);
    int i = 0, j = 0;
    
    while (i < m) {
        if (pattern[j] == text[i]) {
            i++;
            j++;
        }
        if (j == n) {
            return i - j;
        }
        if (i < m && pattern[j] != text[i]) {
            if (j != 0) {
                j = next[j - 1];
            }
            else {
                i++;
            }
        }
    }
    return -1;
}

int main() {
    string text = "ABABCABABDABABCABABC";
    string pattern = "ABABCABABC";
    
    int index = kmp(text, pattern);
    if (index != -1) {
        cout << "匹配成功，起始位置：" << index << endl;
    }
    else {
        cout << "匹配失败！" << endl;
    }
    
    return 0;
}

在上面的代码中，`getNext`函数用于计算模式串的最长公共前后缀数组。KMP算法的关键在于利用该数组来确定匹配失败时的后移位数，从而避免不必要的比较。`kmp`函数则是实现KMP算法的主要逻辑，通过比较字符来查找字符串的匹配位置。

以上是一个简单的KMP算法的实现，可以根据实际需要进行修改和优化。

### 回答3：
KMP算法是一种高效的字符串匹配算法，其核心思想是利用已匹配的部分信息，避免匹配时的重复比较。下面是一个简单的KMP算法的C++代码实现：

#include <iostream>
#include <vector>
using namespace std;

// 计算next数组
void computeNext(const string& pattern, vector<int>& next) {
    int length = pattern.size();
    next[0] = -1;
    int i = 0, j = -1;
    while (i < length - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
}

// KMP算法匹配函数
int kmp(const string& text, const string& pattern) {
    int textLen = text.size();
    int patternLen = pattern.size();
    vector<int> next(patternLen, 0);
    computeNext(pattern, next);
    int i = 0, j = 0;
    while (i < textLen && j < patternLen) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    if (j == patternLen) {
        return i - j; // 返回匹配的起始位置
    } else {
        return -1;    // 未找到匹配
    }
}

int main() {
    string text = "ABABCABABCABC";
    string pattern = "ABCABC";
    int index = kmp(text, pattern);
    if (index != -1) {
        cout << "匹配成功，起始位置为：" << index << endl;
    } else {
        cout << "未找到匹配" << endl;
    }
    return 0;
}

以上代码通过computeNext函数计算出pattern的next数组，然后在kmp函数中利用next数组进行匹配操作。运行结果为：

匹配成功，起始位置为：4