Заменить подстроку в строке не используя replace

Вообще-то один из наиболее эффективных (в т.ч. по производительности) алгоритмов поиска подстроки в строке - алгоритм Бойера-Мура (он же - "алгоритм Бойера-Мура-Хорспула"; его можно загуглить, если лень - вот статья на английском). Уж точно он гораздо эффективнее посимвольного поиска.

Допустим, Вы реализуете этот алгоритм (или будете использовать искать подстроку с помощью 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().

Если всё равно не понятно, то рекомендую попробовать всё это проделать с парой небольших строк на листочке в клеточку вручную (серьёзно, это часто помогает разобраться в алгоритме).

Для тех, кому, возможно, по религиозным соображениям, не подходит "заковыристый алгоритм" поиска подстроки с последующей заменой, могу предложить ещё один вариант решения той же задачи, наиболее близкий к поведению printf:

// <stdarg.h> используется для работы с т.н. элипсисом - переменным списком аргументов,
// обозначаемым троеточием в сигнатуре функции/метода. 
// Из него нам потребуются 4 макроса:
// va_list   - структура, с которой ассоциированы аргументы из элипсиса
// va_start  - начало извлечения аргументов из va_list
// va_arg    - взять очередной аргумент из va_list
// va_end    - завершить работу с va_list
#include <stdarg.h> 


// result_buffer - место под строку, которую хотим получить в итоге
// buffer_size - размер буфера - количество символов в result_buffer 
// format - формат, a'la printf (поддерживает только placeholder-ы - места подстановки - %s и %d)
// ... - любые аргументы в любом количестве (должны быть строго int и char* и соответствовать формату: %d и %s соответственно).
void my_sprintf(char* result_buffer, size_t buffer_size, const char* format, ...) {
    if ((buffer_size < 1)||(!result_buffer))return; // защита от дурака № 1
    
    result_buffer[buffer_size-1] = '\0'; // защита от дурака № 2
    
    va_list ap;
    va_start(ap, format);
    char* pbuffer = result_buffer;//pbuffer будет обозначать текущее место в итоговой строке (буфере)
    while (*format) // Пока не достигли конца строки - '\0'
       if (*format == '%') // Если placeholder (место подстановки в строку)
          if (format[1]) { // Если есть тип данных подставляемых в строку
            switch (format[1]) { // В зависимости от типа данных подставляемых в строку
               case 's':{ // Если в строку подставляем другую строку в стиле Си
                    char* str = va_arg(ap, char *);//взять очередной аргумент-строку
                    const size_t len = strlen(str);//узнать её длину    
                    const size_t remain_len = buffer_size - (pbuffer - result_buffer);//вычислить оставшееся место в буфере
                    const size_t byte_count_to_move = min(len, remain_len);//сколько байт копируем - меньшее между оставшимся местом в буфере и длиной строки
                    memmove(pbuffer, str, byte_count_to_move);//копируем строку в буфер
                    pbuffer += byte_count_to_move;//перемещаем позицию буфера 
               } break;
               case 'd':{ // Если в строку подставляем число в 10чной системе счисления
                   int val = va_arg (ap, int);//взять очередной аргумент-целое
                   char* intstring = itoa(val, pbuffer, 10);//преобразовать в строку
                   while((intstring++)!='\0');//найти нулевой символ
                   pbuffer = intstring;//изменить позицию буфера
               } break;
               default: ++format;//Если какой-то неизвестный тип - пропускаем
            }
          }
          else break;//Если типа подставляемых данных нет == строка кончилсь
       else {//Если не placeholder (место подстановки) - копируем подстроку из строки формата
          const char* format_string_begin = format;//ищем конец строки или начало placeholder-а (места подстановки в строке формата)
          for (; !((*format == '\0')||(*format == '%')); ++format);
          const size_t format_string_len = format - format_string_begin;//вычисляем размер подстроки, перемещаемой в буфер из строки формата
          const size_t remain_len = buffer_size - (pbuffer - result_buffer);//вычисляем оставшееся место в буфере
          const size_t byte_count_to_move = min(format_string_len, remain_len);//вычисляем сколько можно переместить в буфер - наименьшее между длиной строки формата и свободным местом в буфере
          memmove(pbuffer, format_string_begin, byte_count_to_move);//перемещаем
          pbuffer += byte_count_to_move;//смещаем текущую позицию в буфере
       }    
    va_end (ap);
}


int main (int argc, char* argv[]) {
   char buffer[1000];

   my_sprintf(buffer, 1000, "Hello %s*%d", "world", 123); 
   printf("%s\n, buffer); // выведет: Hello world * 123
   return 0;
}