cpp/algorithms/strings/rabin_carp.cpp at master · AllAlgorithms/cpp · GitHub

This repository was archived by the owner on Sep 7, 2025. It is now read-only.

History

71 lines (57 loc) · 1.14 KB

Raw

/**

* C++ Program to Implement Rabin-Karp Algorithm

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cstdlib>

using namespace std;

#define d 256

/**

* Ssearch a substring in a string

void search(char *pat, char *txt, int q)

{

int M = strlen(pat);

int N = strlen(txt);

int i, j;

int p = 0;

int t = 0;

int h = 1;

for (i = 0; i < M - 1; i++)

h = (h * d) % q;

for (i = 0; i < M; i++)

{

p = (d * p + pat[i]) % q;

t = (d * t + txt[i]) % q;

}

for (i = 0; i <= N - M; i++)

{

if (p == t)

{

for (j = 0; j < M; j++)

{

if (txt[i + j] != pat[j])

break;

}

if (j == M)

{

cout << "Pattern found at index: " << i << endl;

}

if (i < N - M)

{

t = (d * (t - txt[i] * h) + txt[i + M]) % q;

if (t < 0)

t = (t + q);

}

int main()

{

char *txt = "This is a sample Testcase";

char *pat = "sam";

int q = 101;

search(pat, txt, q);

return 0;

}

cpp/algorithms/strings/rabin_carp.cpp at master · AllAlgorithms/cpp · GitHub

Uh oh!

Expand file tree

Breadcrumbs

rabin_carp.cpp

Latest commit

History

Breadcrumbs

rabin_carp.cpp

File metadata and controls