A “substitution” is nothing more than the correct copying of the correct (not matching) substrings, inserting a substitution for the matched parts (which is a fairly simple task, completely independent of algorithmic problems!). So, if you know that KMP is the best search subtask algorithm (not like a cut and dried question, as you imagine, in general), it will also be better for “replacing” (especially if you “replace” by creating a new line , as in languages with immutable strings, such as Java and Python - but, nevertheless, even with a language with mutable strings - first determine the matches, then replace ;-).