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:

Go to the source code of this file.

Namespaces
namespace	string_search
	String search algorithms.

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)

Definition in file rabin_karp.cpp.

Macro Definition Documentation

PRIME

#define PRIME   5

Prime modulus for hash functions.

Definition at line 16 of file rabin_karp.cpp.

Function Documentation

main()

int main

(

void

)

Main function

Definition at line 105 of file rabin_karp.cpp.

               {
    assert(rabin_karp("helloWorld", "world") == -1);
    assert(rabin_karp("helloWorld", "World") == 5);
    assert(rabin_karp("this_is_c++", "c++") == 8);
    assert(rabin_karp("happy_coding", "happy") == 0);
    return 0;
}