利用c++数据结构编写代码,要求已知主串S='abc12abcd123efdk1123”.子串T=12,使用堆串存储结构。要求使用KMP 方法找到S中包含的所有子串T并删除,然后输出删除后的串S。
时间: 2024-11-03 19:22:26 浏览: 35
在C++中,我们可以使用KMP算法(Knuth-Morris-Pratt 算法)来查找给定字符串 `S` 中所有匹配子串 `T` 的位置,同时利用堆(如优先队列)来存储匹配的位置,以便后续删除。这里是一个基本的步骤:
首先,我们需要计算部分匹配表(PMT),它是用于KMP搜索的重要辅助数据结构。对于每个字符 `T[i]`,PMT[i]表示最长公共前缀(LCP)的长度。
```cpp
int computePMT(const string &T) {
vector<int> lps(T.size());
int j = 0;
for (int i = 1; i < T.size(); ++i) {
if (T[i] == T[j])
j++;
else if (j > 0)
j = lps[j - 1];
else
lps[i] = 0;
lps[i] = j;
}
return lps;
}
```
接着,我们可以在主字符串上进行KMP搜索,并将每次匹配到的索引加入堆:
```cpp
void findAndRemove(string S, string T, priority_queue<int>& pq) {
int n = S.size();
int m = T.size();
vector<int> lps = computePMT(T);
int i = 0, j = 0;
while (i < n) {
if (S[i] == T[j]) {
i++;
j++;
} else if (j > 0) {
j = lps[j - 1];
} else {
i++;
}
if (j == m) {
pq.push(i - m); // Add the matching index to the heap
j = lps[j - 1]; // Move to the next prefix match
}
}
}
```
最后,遍历堆,删除匹配的子串,并更新剩余的字符串:
```cpp
void removeSubstrings(string& S, const priority_queue<int>& pq) {
while (!pq.empty()) {
int pos = pq.top(); pq.pop();
S.erase(S.begin() + pos, S.begin() + pos + T.size()); // Remove the substring
}
}
```
完整的代码示例:
```cpp
#include <iostream>
#include <string>
#include <queue>
using namespace std;
// ... (previous functions)
int main() {
string S = "abc12abcd123efdk1123";
string T = "12";
priority_queue<int> pq;
findAndRemove(S, T, pq);
removeSubstrings(S, pq);
cout << "After removing all occurrences of " << T << ": " << S << endl;
return 0;
}
```
运行此程序,它将输出删除了所有 "12" 子串后的 `S` 字符串。
阅读全文