C++ 第14题：std::string 全局替换子串算法实现（防死循环指针跳跃）

题目

编写一个高效的全局子串替换函数 replaceAll(std::string& str, const std::string& from, const std::string& to)。将字符串中所有匹配的 from 替换为 to。重点处理经典死循环陷阱：当新子串 to 中包含原旧子串 from 时（例如将 "a" 替换为 "aa"），必须通过精确计算替换后的指针偏移量跳过新插入的内容。

输入格式：第一行输入原文本；第二行输入待替换的目标旧子串；第三行输入替换后的新子串。

输出格式：输出完全替换后的最终字符串。

数据范围与约定：字符串长度 <code>≤ 10^5</code>。

思路与算法

1. 死循环陷阱
如果每次替换完成后仍从当前 pos 重新 find(from, pos)，当 to 包含 from 时，程序会陷入死循环直到内存耗尽崩溃。

2. 精确位移步进
使用 str.replace(pos, from.length(), to) 完成替换后，下次查找的起始位置必须设置为 pos + to.length()，直接跃过刚刚注入的新内容。

3. 空子串防御
若 from.empty()，必须直接短路返回，否则 find("", pos) 将永远返回当前 pos 导致致命死循环。

完整程序

#include <iostream>
#include <string>

void replaceAll(std::string& str, const std::string& from, const std::string& to) {
    if (from.empty()) {
        return; // 防御空串匹配死循环
    }

    std::string::size_type startPos = 0;
    while ((startPos = str.find(from, startPos)) != std::string::npos) {
        str.replace(startPos, from.length(), to);
        // 关键：跳过刚刚替换插入的新子串整体长度
        startPos += to.length();
    }
}

int main() {
    std::string text, from, to;
    if (!std::getline(std::cin, text) || !std::getline(std::cin, from) || !std::getline(std::cin, to)) {
        return 0;
    }

    std::cout << "替换前原串: " << text << "\n";
    replaceAll(text, from, to);
    std::cout << "替换后结果: " << text << "\n";

    return 0;
}

运行示例

示例 1：

输入：

user_id = %id%, user_name = %id%_name
%id%
admin

输出：

替换前原串: user_id = %id%, user_name = %id%_name
替换后结果: user_id = admin, user_name = admin_name

示例 2：

输入：

banana
a
aa

输出：

替换前原串: banana
替换后结果: baanaanaa