Algorithms_in_C++  1.0.0
Set of algorithms implemented in C++.
rabin_karp.cpp File Reference

The Rabin-Karp Algorithm for finding a pattern within a piece of text with complexity O(n + m) More...

#include <cassert>
#include <cmath>
#include <iostream>
#include <cstring>
Include dependency graph for rabin_karp.cpp:

Namespaces

 

Macros

#define PRIME   5
 Prime modulus for hash functions.
 

Functions

int64_t string_search::create_hash (const std::string &s, int n)
 
int64_t string_search::recalculate_hash (const std::string &s, int old_index, int new_index, int64_t old_hash, int patLength)
 
bool string_search::check_if_equal (const std::string &str1, const std::string &str2, int start1, int end1, int start2, int end2)
 
int string_search::rabin_karp (const std::string &str, const std::string &pat)
 
int main (void)
 

Detailed Description

The Rabin-Karp Algorithm for finding a pattern within a piece of text with complexity O(n + m)

Function Documentation

◆ main()

int main ( void  )

Main function

105  {
106  assert(rabin_karp("helloWorld", "world") == -1);
107  assert(rabin_karp("helloWorld", "World") == 5);
108  assert(rabin_karp("this_is_c++", "c++") == 8);
109  assert(rabin_karp("happy_coding", "happy") == 0);
110  return 0;
111 }
Here is the call graph for this function:
string_search::rabin_karp
int rabin_karp(const std::string &str, const std::string &pat)
Definition: rabin_karp.cpp:83