Вообще-то один из наиболее эффективных (в т.ч. по производительности) алгоритмов поиска подстроки в строке - алгоритм Бойера-Мура (он же - "алгоритм Бойера-Мура-Хорспула"; его можно загуглить, если лень - вот статья на английском). Уж точно он гораздо эффективнее посимвольного поиска.
Допустим, Вы реализуете этот алгоритм (или будете использовать искать подстроку с помощью C++17 - используя std::search + std::boyer_moore_searcher). Тогда, на выходе у Вас могут быть индексы/указатели/итераторы - в зависимости от используемого алгоритма - так или иначе определяющие границы найденной подстроки. Далее, я буду, для краткости, использовать обобщённый термин "итератор", но не в буквальном смысле итераторов C++, а в широком смысле такой абстракции как "итератор", каковой являются не только итераторы C++, но также и указатели или индексы.
Итак, так или иначе, в результате любого поиска подстроки в строке (при её наличии), Вы имеете итераторы, определяющие границы этой подстроки.
Будем считать, что для любой строки, в т.ч. найденной в результате поиска подстроки, определены следующие итераторы: Begin - начало строки, Size - количество символов в строке, End - конец строки - символ, следующий за последним, такие, что для них верны все следующие уравнения:
End - Begin = Size;
Begin + Size = End;
End - Size = Begin;
Будем также считать, что String - вся строка целиком, в которой осуществляется поиск, а Substring - подстрока, найденная в строке String.
Тогда, получим следующее (псевдокод на C++):
// Шаг 1 - найти подстроку:
string_view Substring("substring");
auto Begin = find_substring(String, Substring);//алгоритм find_substring - на Ваше усмотрение любой, позволяющий найти подстроку, например - предложенный мной выше Бойер-Мур
// Шаг 2 - заменить подстроку на что-то другое
string NewString; // Новая строка
// Ключевое действие: выделяем место под количество символов,
// достаточное для хранения новой строки. Нам нужно:
// Вычесть из размера исходной строки размер заменяемой подстроки и
// прибавить размер той строки, которой хотим заменить заменяемую:
NewString.resize(String.size() - Substring.size() + ReplacementString.size());
// Далее воспользуемся читерством в стиле C - функцией побайтового копирования:
// Шаг 1: перемещаем левую часть исходной строки, до заменяемой подстроки, в новую строку:
memmove(NewString.data(), String.data(), sizeof(string::char_type) * (Begin - String.begin())); // sizeof(string::char_type) - размер символа (1 байт, если char_type это char); (Begin - String.begin()) - длина левой части исходной строки, до найденной подстроки
// Шаг 2: перемещаем середину - замещающую подстроку:
memmove(NewString.data() + (Begin - String.begin()), ReplacementString.data(), sizeof(string::char_type) * ReplacementString.size());
// Шаг 3: перемещаем правую часть исходной строки, следующую после заменяемой подстроки:
memmove(NewString.data() + (Begin - String.begin()) + ReplacementString.size(),
Begin + Substring.size(),
sizeof(string::char_type) * (String.end() - (Begin + Substring.size())));
//(String.end() - (Begin + Substring.size())) - оставшееся количество символов, которые нужно переместить:
//Символ, следующий за последним в исходной строке, за вычетом символа,
//следующего за последним в найденной подстроке (его положение в исходной строке)
// Итог: заменена подстрока в строке: строка NewString содержит строку,
// полученную путём замены подстроки Substring строкой ReplacementString в строке String.
// Дальше можно вызвать clear и shrink_to_fit на всех строках, кроме NewString - она и есть результат замены.
Обращаю внимание: если ReplacementString.size() > Substring.size(), то выделять дополнительную память/создавать отдельную строку NewString придётся 100%. Если же ReplacementString.size() <= Substring.size(), то можно обойтись и строкой String, не создавать NewString. При этом, принцип останется тем же, только можно будет пропустить 1й шаг (перемещение в памяти): 1я часть строки String, которая до Substring, уже на месте, останется лишь передвинуть ReplacementString на позицию Begin, а потом, на позицию Begin + ReplacementString.string() сдвинуть ту часть исходной строки String, которая была после Begin + Substring.size() до String.end().
Если всё равно не понятно, то рекомендую попробовать всё это проделать с парой небольших строк на листочке в клеточку вручную (серьёзно, это часто помогает разобраться в алгоритме).