Bizda quyidagi matn bor bo’lsin

Output
Pattern found at index 0
Pattern found at index 10
Time Complexity: 

• 
  The average and best-case running time of the Rabin-Karp algorithm is O(n+m), but its worst-case time is O(nm).
  
• 
  The worst case of the Rabin-Karp algorithm occurs when all characters of pattern and text are the same as the hash values of all the substrings of txt[] match with the hash value of pat[]. 
  

Auxiliary Space: O(1)
Related Posts: 
Searching for Patterns | Set 1 (Naive Pattern Searching) 
Searching for Patterns | Set 2 (KMP Algorithm)
Please write comments if you find anything incorrect, or if you want to share more information about the topic discussed above.

Алгоритм Рабина-Карпа с полиномиальным хешем и модульной арифметикой

Введение

Созданный Ричардом Карпом и Майклом Рабином алгоритм Рабина-Карпа — это алгоритм поиска строки, который использует хеширование для поиска совпадений между заданным шаблоном поиска и текстом.
Наивный алгоритм поиска строки сравнивает заданный шаблон со всеми позициями в тексте. Это приводит к далеко не идеальной сложности времени исполнения O(nm), где n = длина текста, а m = длина шаблона.
Алгоритм Рабина-Карпа совершенствует этот подход за счёт того, что сравнение хешей двух строк выполняется за линейное время: для поиска совпадения это гораздо эффективнее, чем сравнение отдельных символов этих строк. Таким образом, алгоритм показывает лучшее время исполнения O(n+m).

Алгоритм Рабина-Карпа

1. 
   Вычисляется хеш шаблона строки.
   
2. 
   Вычисляется хеш подстроки в тексте строки, начиная с индекса 0 и до m-1.
   
3. 
   Сравнивается хеш подстроки текста с хешем шаблона.
   

• 
  Если они совпадают, то сравниваются отдельные символы для выявления точного совпадения двух строк.
  
• 
  Если они не совпадают, то окно подстроки сдвигается путём увеличения индекса и повторяется третий пункт для вычисления хеша следующих m символов, пока не будут пройдены все n символов.