-
-
Save SuryaPratapK/a76f8d62a915e649023eb900a944c8fe to your computer and use it in GitHub Desktop.
/* Following program is a C++ implementation of Rabin Karp | |
Algorithm given in the CLRS book */ | |
#include <bits/stdc++.h> | |
using namespace std; | |
// d is the number of characters in the input alphabet | |
#define d 256 | |
/* pat -> pattern | |
txt -> text | |
q -> A prime number | |
*/ | |
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++) | |
{ | |
// Check the hash values of current window of text | |
// and pattern. If the hash values match then only | |
// check for characters on by one | |
if ( p == t ) | |
{ | |
/* Check for characters one by one */ | |
for (j = 0; j < M; j++) | |
{ | |
if (txt[i+j] != pat[j]) | |
break; | |
} | |
// if p == t and pat[0...M-1] = txt[i, i+1, ...i+M-1] | |
if (j == M) | |
cout<<"Pattern found at index "<< i<<endl; | |
} | |
// Calculate hash value for next window of text: Remove | |
// leading digit, add trailing digit | |
if ( i < N-M ) | |
{ | |
t = (d*(t - txt[i]*h) + txt[i+M])%q; | |
// We might get negative value of t, converting it | |
// to positive | |
if (t < 0) | |
t = (t + q); | |
} | |
} | |
} | |
/* Driver code */ | |
int main() | |
{ | |
char txt[] = "GEEKS FOR GEEKS"; | |
char pat[] = "GEEK"; | |
int q = 101; // A prime number | |
search(pat, txt, q); | |
return 0; | |
} | |
// This is code is contributed by rathbhupendra |
Can you explain this : for (int i = 0; i < pat.size(); i++)
{
hpat *= d;
hpat = hpat + (((pat[i] - 'A' + 1)) % p);
}
GFG solution
🤣🤣🤣🤣
import java.nio.file.Path;
import java.util.*;
public class Solution
{
private static final int d = 26; // Base value of alphabets
private static final int p = 5381; // Large prime number
public static void search(String pat, String txt)
{
int patHash = 0; // Hash value of pattern
int txtHash = 0; // Hash value of text
for (int i = 0; i < pat.length(); i++) // Generating Hash values for pattern and first window text
{
patHash = patHash * d;
txtHash = txtHash * d;
patHash = patHash + ((pat.charAt(i) - 'A' + 1) % p);
txtHash = txtHash + ((txt.charAt(i) - 'A' + 1) % p);
}
for (int i = 0; i < txt.length() - pat.length(); i++) // Loop of text size minus window
{
if (patHash == txtHash)
{
System.out.println("Pattern found at index " + i);
}
if (i < txt.length() - pat.length())
{
txtHash = txtHash - ((txt.charAt(i) - 'A' + 1) * (int)Math.pow(d, pat.length() - 1)); // Subtracting first element from current hash of d^window-1
txtHash = txtHash * d + (txt.charAt(i + pat.length()) - 'A' + 1); // multiplying obtained hash with d to left shift the number and then adding the next new element
}
}
}
public static void main(String []args)
{
String txt = "GEEKS FOR GEEKS";
String pat = "GEEK";
search(pat, txt);
}
}
import java.nio.file.Path; import java.util.*; public class Solution { private static final int d = 26; // Base value of alphabets private static final int p = 5381; // Large prime number public static void search(String pat, String txt) { int patHash = 0; // Hash value of pattern int txtHash = 0; // Hash value of text for (int i = 0; i < pat.length(); i++) // Generating Hash values for pattern and first window text { patHash = patHash * d; txtHash = txtHash * d; patHash = patHash + ((pat.charAt(i) - 'A' + 1) % p); txtHash = txtHash + ((txt.charAt(i) - 'A' + 1) % p); } for (int i = 0; i < txt.length() - pat.length(); i++) // Loop of text size minus window { if (patHash == txtHash) { System.out.println("Pattern found at index " + i); } if (i < txt.length() - pat.length()) { txtHash = txtHash - ((txt.charAt(i) - 'A' + 1) * (int)Math.pow(d, pat.length() - 1)); // Subtracting first element from current hash of d^window-1 txtHash = txtHash * d + (txt.charAt(i + pat.length()) - 'A' + 1); // multiplying obtained hash with d to left shift the number and then adding the next new element } } } public static void main(String []args) { String txt = "GEEKS FOR GEEKS"; String pat = "GEEK"; search(pat, txt); } }
for (int i = 0; i < txt.length() - pat.length(); i++)
I think this loop should run till ( i<= txt.length() - pat.length() ) as your loop is not able to match the pattern present at the end of the string
correct me if I'm wrong
https://leetcode.com/problems/longest-duplicate-substring/
apply this and solve for practice
#include <bits/stdc++.h>
using namespace std;
int main() { string txt = "AABAACBAA", pat = "BAA"; int hpat=0,htxt=0; int d = 26; int p = 5381; for (int i = 0; i < pat.size(); i++) { hpat *= d; hpat = hpat + (((pat[i] - 'A' + 1)) % p); } int l=0, r = 0; while (r < txt.size()){ htxt *= d; htxt = htxt + ((txt[r] - 'A' + 1) % p); if(r-l+1==pat.size()){ if(htxt==hpat) cout << "Match at " << l; htxt = htxt - (((txt[l] - 'A' + 1) * pow(d, r - l))); l++; } r++; } return 0; }
this will give runtime error: signed integer overflow: 408244051 * 26 cannot be represented in type 'int' .
import java.nio.file.Path; import java.util.*; public class Solution { private static final int d = 26; // Base value of alphabets private static final int p = 5381; // Large prime number public static void search(String pat, String txt) { int patHash = 0; // Hash value of pattern int txtHash = 0; // Hash value of text for (int i = 0; i < pat.length(); i++) // Generating Hash values for pattern and first window text { patHash = patHash * d; txtHash = txtHash * d; patHash = patHash + ((pat.charAt(i) - 'A' + 1) % p); txtHash = txtHash + ((txt.charAt(i) - 'A' + 1) % p); } for (int i = 0; i < txt.length() - pat.length(); i++) // Loop of text size minus window { if (patHash == txtHash) { System.out.println("Pattern found at index " + i); } if (i < txt.length() - pat.length()) { txtHash = txtHash - ((txt.charAt(i) - 'A' + 1) * (int)Math.pow(d, pat.length() - 1)); // Subtracting first element from current hash of d^window-1 txtHash = txtHash * d + (txt.charAt(i + pat.length()) - 'A' + 1); // multiplying obtained hash with d to left shift the number and then adding the next new element } } } public static void main(String []args) { String txt = "GEEKS FOR GEEKS"; String pat = "GEEK"; search(pat, txt); } }
You should change the loop condition to i <= txt.length() - pat.length() instead of i < txt.length() - pat.length(); the( <= )
#include <bits/stdc++.h>
using namespace std;
int main()
{
string txt = "AABAACBAA", pat = "BAA";
int hpat=0,htxt=0;
int d = 26;
int p = 5381;
for (int i = 0; i < pat.size(); i++)
{
hpat *= d;
hpat = hpat + (((pat[i] - 'A' + 1)) % p);
}
int l=0, r = 0;
while (r < txt.size()){
htxt *= d;
htxt = htxt + ((txt[r] - 'A' + 1) % p);
if(r-l+1==pat.size()){
if(htxt==hpat)
cout << "Match at " << l;
htxt = htxt - (((txt[l] - 'A' + 1) * pow(d, r - l)));
l++;
}
r++;
}
return 0;
}