Algorithms_in_C++ 1.0.0
Set of algorithms implemented in C++.
Loading...
Searching...
No Matches
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}