Para string, localize e substitua

Encontrar um texto e substituí-lo por um novo texto em uma string C pode ser um pouco mais complicado do que o esperado. Estou procurando por um algoritmo que seja rápido e que tenha uma pequena complexidade de tempo.

O que devo usar?