What's the most efficient algorithm for string replacing?

KMP is for searching,what's the one for replacing?

"Replacing" is nothing more than correct copying of the right (non-matched) substrings, while inserting the substitution for the matched pieces (which is a pretty trivial task, quite independent of algorithmic issues!-). So, if you know that KMP is the best algorithm for the searching subtask (not as cut-and-dried an issue as you present it, in the general case), it will also be best for "replacing" (especially if you "replace" by making a new string, as you do in languages with immutable strings like Java and Python -- but, nevertheless, even with a mutable-strings language -- just identify matches first, THEN do the replaces;-).