Bizda quyidagi matn bor bo’lsin

Сложность

С учётом длины слова m и длины текста n в лучшем случае временная сложность будет составлять O(n + m), а пространственная сложность — O(m). Временная сложность в худшем случае будет O(nm). Это может произойти при выборе очень плохо работающей хеш-функции. Решить эту проблему может хорошая хеш-функция, такая как полиномиальный хеш.

Заключение

Несмотря на наличие более производительных алгоритмов поиска одиночных строк, алгоритм Рабина-Карпа может оказаться довольно эффективным при поиске множественных шаблонов. Он обеспечивает прочную основу для расширения вариантов применения в этой проблемной области.
Читайте также:

• 
  Как освоить алгоритмы?
  
• 
  10 Графовых алгоритмов
  
• 
  Графы: основы теории, алгоритмы поиска
  

Читайте нас в Telegram, VK и Яндекс.Дзен
Перевод статьи Vigar Block: Rabin-Karp Algorithm Using Polynomial Hashing and Modular Arithmetic

Computer Science


Nuances Of Programming


Karp Rabin


String Search


Algorithms

22

More from NOP::Nuances of Programming

Follow
Образовательные статьи и переводы — всё для программиста

Дмитрий ПереводIT

·Nov 15, 2020

Обработка ошибок в Go

Обработка ошибок в Go постоянно вызывает споры и возникает среди тем ежегодного опроса о сложнейших проблемах, с которыми встречаются разработчики, пишущие на этом языке. Тем не менее, когда дело доходит до работы с ошибками в конкурентной среде или объединении ошибок одной горутины, Go предлагает отличные пакеты, которые упрощают их обработку…

Go

4 min read

Share your ideas with millions of readers.

Write on Medium

Дмитрий ПереводIT

·Nov 14, 2020