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)
int	rabin_karp (const std::string &str, const std::string &pat)

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;
}

rabin_karp()

int string_search::rabin_karp	(	const std::string &	str,
		const std::string &	pat )

Perform string pattern search using Rabin-Karp algorithm

Parameters

[in]	str	string to search in
[in]	pat	pattern to search for

Returns

index of first occurrence of pattern

-1 if pattern not found

Definition at line 83 of file rabin_karp.cpp.

                                                           {
    int64_t pat_hash = create_hash(pat, pat.size());
    int64_t str_hash = create_hash(str, pat.size());
    for (int i = 0; i <= str.size() - pat.size(); ++i) {
        if (pat_hash == str_hash &&
            check_if_equal(str, pat, i, i + pat.size() - 1, 0,
                           pat.size() - 1)) {
            return i;
        }
        if (i < str.size() - pat.size()) {
            str_hash =
                recalculate_hash(str, i, i + pat.size(), str_hash, pat.size());
        }
    }
    return -1;  // return -1 if given pattern not found
}