Какой самый эффективный алгоритм для замены строк?

Question

KMP предназначен для поиска, что для замены?

Answer 1

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