Какие существуют эффективные алгоритмы поиска и замены подстрок в строках?

Некоторые эффективные алгоритмы поиска подстрок в строках:

• Алгоритм Рабина-Карпа. neerc.ifmo.ru Прямой алгоритм, использует хэширование, что в среднем снижает скорость. neerc.ifmo.ru Можно модифицировать для поиска нескольких паттернов. neerc.ifmo.ru
• Алгоритм Кнута-Морриса-Пратта. neerc.ifmo.ru habr.com Прямой алгоритм, использует префикс-функцию. neerc.ifmo.ru
• Алгоритм Колусси. neerc.ifmo.ru Прямой алгоритм, использует тот факт, что в современных процессорах битовые сдвиг и или являются атомарными. neerc.ifmo.ru Эффективен, если p ≤ w. neerc.ifmo.ru Иначе деградирует и по памяти, и по сложности. neerc.ifmo.ru
• Алгоритм Бойера-Мура. neerc.ifmo.ru Обратный алгоритм, считается наиболее быстрым из алгоритмов общего назначения. neerc.ifmo.ru Использует эвристики, существует большое количество оптимизаций. neerc.ifmo.ru
• Поиск подстроки в строке с помощью суффиксного массива. neerc.ifmo.ru Прямой алгоритм, использует суффиксный массив. neerc.ifmo.ru
• Поиск подстроки в строке с помощью суффиксного дерева. neerc.ifmo.ru

Для замены подстрок в строках можно использовать метод replace. foxford.ru Он заменяет все вхождения одной строки на другую. foxford.ru Если методу задать ещё один параметр, то заменены будут не все вхождения, а только не больше, чем первые count из них. foxford.ru