编程题，1、模式匹配算法的实现；2、利用模式匹配算法实现删除主串中所有包含子串的字符。

1、KMP算法的实现

KMP算法，全称为Knuth-Morris-Pratt算法，是一种用来解决模式串在文本串是否出现过的问题的字符串匹配算法，KMP算法的核心是构造前缀表，通过前缀表来进行匹配，时间复杂度为O(m+n)，其中m为模式串长度，n为文本串长度。

以下是KMP算法的C++实现：

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

void getNext(string pattern, int* next) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}

int kmp(string text, string pattern) {
    int* next = new int[pattern.size()];
    getNext(pattern, next);
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == pattern.size()) {
            return i - j + 1;
        }
    }
    delete[] next;
    return -1;
}

int main() {
    string text = "hello world";
    string pattern = "world";
    int pos = kmp(text, pattern);
    if (pos != -1) {
        cout << "pattern found at position " << pos << endl;
    }
    else {
        cout << "pattern not found" << endl;
    }
    return 0;
}

2、利用KMP算法实现删除主串中所有包含子串的字符

思路：对于主串中的每个位置，判断以该位置为起点的子串是否包含子串，如果包含，则将该位置后的字符向前移动子串长度的距离。

以下是实现代码：

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

void getNext(string pattern, int* next) {
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < pattern.size(); i++) {
        while (j > 0 && pattern[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (pattern[i] == pattern[j]) {
            j++;
        }
        next[i] = j;
    }
}

void removeSubstr(string& text, string pattern) {
    int* next = new int[pattern.size()];
    getNext(pattern, next);
    int j = 0;
    for (int i = 0; i < text.size(); i++) {
        while (j > 0 && text[i] != pattern[j]) {
            j = next[j - 1];
        }
        if (text[i] == pattern[j]) {
            j++;
        }
        if (j == pattern.size()) {
            // 删除子串
            text.erase(i - j + 1, j);
            i -= j; // 回退i的位置
            j = 0;  // 重置j的值
        }
    }
    delete[] next;
}

int main() {
    string text = "hello world";
    string pattern = "lo";
    removeSubstr(text, pattern);
    cout << text << endl; // 输出"h wrd"
    return 0;
}

以上就是模式匹配算法的实现以及利用模式匹配算法实现删除主串中所有包含子串的字符的代码实现。