C++编写代码 已知主串S=‘abc12abcd123efdk1123’，子串T=‘12’，使用堆串存储结构。要求使用KMP方法找到s中包含的所有子串T并删除，然后输出删除后的S

在C++中，我们可以使用KMP算法（Knuth-Morris-Pratt算法）结合堆栈数据结构来实现这个需求。首先，我们需要创建一个辅助函数来计算部分匹配表（Partial Match Table，简称PMT），用于存储子串T的前缀到后缀的最长相等序列长度。接着，我们会遍历主串S，利用PMT进行搜索，并使用堆栈记录每个匹配的位置。每当遇到子串T时，我们从S中移除它，并更新剩余部分。

以下是步骤概述：

1. **创建部分匹配表**（PMT）：
- 初始化一个数组p，长度等于T的长度。
- p[0] = 0，因为前缀和空字符串有相同的长度。
- 使用滑动窗口法，逐位比较T[i]和T[j], 如果相等且j + 1 < T.length(), 则p[i] = j + 1; 否则, p[i] = p[j].

2. **主循环**：
- 初始化两个指针i (主串索引) 和 j (子串索引), i = j = 0.
- 当i < S.length()时：
- 如果S[i] == T[j]:
- i++, j++
- 如果j >= T.length() 或者 S[i] != T[j]:
- 如果j > 0, 更新i = i + p[j - 1]; // 滑回寻找下一个可能的匹配点
- j = 0 // 如果没有找到匹配，重置j.

3. **找到子串并删除**：
- 当找到子串T时 (j == T.length())，记录位置并移除S的相应部分。
- 可能需要使用容器（如std::string的substr方法）或动态内存管理来替换子串区域。

4. **输出结果**：
- 删除所有找到的子串T后，输出处理过的字符串S。

下面是一个简单的伪代码示例：

// 假设S和T是字符串
int PMT[T.length()];
...
for (int i = 1; i < T.length(); ++i)
    PMT[i] = (T[i] == T[i - 1]) ? PMT[i - 1] : 0;

// 主循环
std::stack<int> indices;
for (int i = 0; i < S.length(); ++i) {
    if (i < T.length() && S.substr(i, T.length()) == T) {
        indices.push(i);
        i += T.length() - 1; // 跳过已找到的部分
    }
    else if (!indices.empty()) {
        int lastMatchIndex = indices.top();
        indices.pop();
        S.erase(S.begin() + lastMatchIndex, S.begin() + lastMatchIndex + T.length());
    }
}

std::cout << "删除子串后的S: " << S << std::endl;