«Замена» - это не что иное, как правильное копирование правильных (не совпадающих) подстрок при вставке подстановки для совпадающих фрагментов (что является довольно тривиальной задачей, совершенно независимой от алгоритмических проблем! -). Таким образом, если вы знаете , что KMP является лучшим алгоритмом для подзадачи поиска (в общем случае это не такая сложная проблема, как вы представляете), она также будет лучше для "замены". «(особенно если вы« заменяете »путем создания новой строки, как это происходит в языках с неизменяемыми строками, такими как Java и Python, - но, тем не менее, даже с языком изменяемых строк - сначала просто идентифицируйте совпадения, ТО затем выполняйте замены ; -).