Scribd
Upload
41 views

Naïve Method. Code:: Naive, Rabin-Karp, and Knuth-Morris-Pratt Algorithms For String Matching

This document describes and provides code examples for three string matching algorithms: Naive, Rabin-Karp, and Knuth-Morris-Pratt. The naive algorithm compares characters one by one at each index. Rabin-Karp uses hashing to optimize the search. Knuth-Morris-Pratt uses a partial match table to skip matching for already compared prefixes. Code examples in C++ are provided for each algorithm.

Uploaded by

Hakuna-29 matata
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
41 views

Naïve Method. Code:: Naive, Rabin-Karp, and Knuth-Morris-Pratt Algorithms For String Matching

This document describes and provides code examples for three string matching algorithms: Naive, Rabin-Karp, and Knuth-Morris-Pratt. The naive algorithm compares characters one by one at each index. Rabin-Karp uses hashing to optimize the search. Knuth-Morris-Pratt uses a partial match table to skip matching for already compared prefixes. Code examples in C++ are provided for each algorithm.

Uploaded by

Hakuna-29 matata
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 5

Naive, Rabin-Karp, and Knuth-Morris-Pratt algorithms for

string matching.
By Devansh Kumar (2K19/MC/037)

Naïve Method.
Code:
#include<bits/stdc++.h>
using namespace std;

void search(char* pat, char* txt){


int M = strlen(pat);
int N = strlen(txt);
for (int i = 0; i <= N - M; i++) {
int j;
// For current index i, check for pattern match
for (j = 0; j < M; j++)
if (txt[i + j] != pat[j])
break;
if (j == M)
printf("Pattern found at index %d \n", i);
}
}

int main(){
cout<<"Finding the pattern from the text using naive approach.\n";
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
cout<<"The text: "<<txt<<endl<<"The pattern: "<<pat<<endl;
search(pat, txt);
return 0;
}

Output:

Submitted to: Mr. Dhirendra kumar (CS-262)


Rabin-Karp Method.
Code:
#include <bits/stdc++.h>
using namespace std;
// d is the number of characters in the input
#define d 256

void search(char pat[], char txt[], int q){


int M = strlen(pat);
int N = strlen(txt);
int i, j;
int p = 0; // hash value for pattern
int t = 0; // hash value for txt
int h = 1;

// The value of h would be "pow(d, M-1)%q"


for (i = 0; i < M - 1; i++)
h = (h * d) % q;

// Calculate the hash value of pattern and first window of text


for (i = 0; i < M; i++){
p = (d * p + pat[i]) % q;
t = (d * t + txt[i]) % q;
}

// Slide the pattern over text one by one


for (i = 0; i <= N - M; i++){
if ( p == t ){
/* Check for characters one by one */
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);
}
}
}

Submitted to: Mr. Dhirendra Kumar sir


int main(){
cout<<"Finding the pattern from the text using Rabin Karp method.\n";
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
cout<<"The text: "<<txt<<endl<<"The pattern: "<<pat<<endl;
// A prime number
int q = 101;
// Function Call
search(pat, txt, q);
return 0;
}

Output:

Submitted to: Mr. Dhirendra Kumar (CS-262)


Knuth-Morris Method.
Code:
#include <bits/stdc++.h>
using namespace std;

void computeLPSArray(char* pat, int M, int* lps);

void KMPSearch(char* pat, char* txt){


int M = strlen(pat);
int N = strlen(txt);
int lps[M];
// Preprocess the pattern (calculate lps[] array)
computeLPSArray(pat, M, lps);
int i = 0; // index for txt[]
int j = 0; // index for pat[]
while (i < N) {
if (pat[j] == txt[i]) {
j++;
i++;
}
if (j == M) {
printf("Found pattern at index %d \n ", i - j);
j = lps[j - 1];
}
// mismatch after j matches
else if (i < N && pat[j] != txt[i]) {
// Do not match lps[0..lps[j-1]] characters, they will match anyway
if (j != 0)
j = lps[j - 1];
else
i = i + 1;
}
}
}

void computeLPSArray(char* pat, int M, int* lps){


int len = 0;
lps[0] = 0;
int i = 1;
while (i < M) {
if (pat[i] == pat[len]) {
len++;
lps[i] = len;
i++;
}
Submitted to: Mr. Dhirendra Kumar sir
else // (pat[i] != pat[len])
{
if (len != 0) {
len = lps[len - 1];
}
else // if (len == 0)
{
lps[i] = 0;
i++;
}
}
}
}

int main(){
cout<<"Finding the pattern from the text using KMP Algorithm.\n";
char txt[] = "AABAACAADAABAAABAA";
char pat[] = "AABA";
cout<<"The text: "<<txt<<endl<<"The pattern: "<<pat<<endl;
KMPSearch(pat, txt);
return 0;
}

Output:

Submitted to: Mr. Dhirendra Kumar (CS-262)

You might also like