已知字符串S采用顺序存储结构,设计一个算法,从S中删除所有与串T相同的子串。
时间: 2023-06-19 21:09:19 浏览: 289
可以使用双指针的方法,遍历字符串S,当遇到与字符串T第一个字符相同时,比较S中当前位置后的子串是否与T相同,若相同则删除该子串,继续向后遍历。具体步骤如下:
1. 定义双指针i和j,初始值均为0。
2. 从左到右遍历字符串S,当S[i]等于T[0]时,进入子串匹配流程。
3. 双指针j从i开始向后移动,同时用一个辅助指针k遍历T,比较S[j]和T[k]是否相同。如果相同,k和j同时向后移动;如果不同,退出子串匹配流程。
4. 如果k能够遍历完T,说明S[i]到S[j]这段子串与T相同,删除该子串。具体实现可以使用S.erase(i, j-i+1)方法。
5. 继续从S[j]向后遍历,重复上述步骤,直到S遍历结束。
以下是该算法的C++代码实现:
```
void deleteAllSubstr(string& S, string T) {
int i = 0, j, k;
while (i < S.length()) {
if (S[i] == T[0]) {
j = i;
k = 0;
while (j < S.length() && k < T.length() && S[j] == T[k]) {
j++;
k++;
}
if (k == T.length()) {
S.erase(i, j-i);
}
else {
i++;
}
}
else {
i++;
}
}
}
```
阅读全文
相关推荐













