c++算法题

题目

字符串的替换操作 replace(String &s, String &t, String &v) 是指：

若t是s的子串，则用串v替换串t在串s中的所有出现；若t不是s的子串，则串s不变。例如，若串s为“aabbabcbaabaaacbab”，串t为“bab”，串v为“abdc”，则执行replace操作后，串s中的结果为“aababdccbaabaaacabdc”。试利用字符串的基本运算实现这个替换操作。

分析

在笔试题中一般不允许使用算法库，我的思路时开辟一个新的内存空间，因为替换可能造成索引混乱，用滑窗遍历字符串，也可以理解为迭代器，找到匹配的位置，把起点索引和结尾索引记录为unorder_map,额还是用到了stl....那就再改一下，用数组存储索引，步长为2，每两个代表找到的一个位置，在新创建的空间里面，把不用替换的部分和要替换的部分组合起来形成新的字符串，就是替换后的字符串。笔试题不会这么复杂吧，这么复杂我选择不写耽误时间。

实现

上面那个量大了，笔试那样写时间够不够都不好说，就改用string的find和replace实现。自定义全局的替换函数，每次找到的字符串直接进行替换然后更新查找的起始位置

#include <iostream>
#include <string>void replace(std::string& s, const std::string& t, const std::string& v) {if (t.empty()) return; // 空子串直接返回size_t start_pos = 0;while ((start_pos = s.find(t, start_pos)) != std::string::npos) {s.replace(start_pos, t.length(), v);start_pos += v.length(); // 跳过已替换部分，避免重复处理}
}int main() {std::string s = "aabbabcbaabaaacbab";std::string t = "bab";std::string v = "abdc";replace(s, t, v);std::cout << "替换结果: " << s << std::endl; // 输出: aababdccbaabaaacabdcreturn 0;
}