SuryaPratapK/Rabin_Karp_Algo_Rolling_Hash

9540621011 · 2021-03-09T09:20:17Z

GFG solution

deekshith39 · 2021-03-26T12:43:35Z

Sorry, I couldn't make it to GFG

adityarawat1337x · 2021-05-20T06:37:35Z

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

ShreyBansal22 · 2021-07-06T16:41:11Z

Can you explain this : for (int i = 0; i < pat.size(); i++)
{
hpat *= d;
hpat = hpat + (((pat[i] - 'A' + 1)) % p);
}

rohit2sAahu · 2021-07-20T15:40:12Z

GFG solution

🤣🤣🤣🤣

SushantPatial · 2021-08-12T19:37:35Z

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

akshat-fsociety · 2021-09-02T08:04:22Z

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

babluparihar · 2021-10-30T14:07:30Z

https://leetcode.com/problems/longest-duplicate-substring/

apply this and solve for practice

mohit421 · 2022-09-15T15:45:16Z

#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' .

xsanket · 2024-01-18T06:59:03Z

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( <= )

Blade2Cruzor · 2024-12-12T10:47:23Z

package gfg;

import java.util.ArrayList;
import java.util.List;

public class RabinKarpRollHash
{
	 private static final int d = 26; // Base value of alphabets
	 private static final int p = 5381; // Large prime number
	
	private List<Integer> rollHash(String pattern, String text)
	{
		List<Integer> indices = new ArrayList<Integer>();
		int patHash = 0;
		int txtHash = 0;
		
		for (int i = 0,pow = pattern.length() - 1; i < pattern.length(); i++) // Generating Hash values for pattern and first window text
	    {
			patHash += (pattern.charAt(i) - 'A' + 1) * (int)Math.pow(d, pow);
			patHash %= p;
			txtHash += (text.charAt(i) - 'A' + 1) * (int)Math.pow(d, pow--);
			txtHash %= p;
	    }

		for (int i = 0; i <= text.length() - pattern.length(); i++)
		{
			//declaration
			String textToCompare = text.substring(i, i + pattern.length());
			int pow = pattern.length() - 1;
			
			//condition for matched pattern
			if (patHash == txtHash && match(textToCompare, pattern))
			{
				indices.add(i + 1);
			}
			
			//calculate hash till last pattern string
			if(i < text.length() - pattern.length())
			{
				//subtract
				txtHash = txtHash - (((text.charAt(i) - 'A' + 1) * (int)Math.pow(d, pow)) % p);
				//add
				txtHash = ((txtHash * d) + (text.charAt(i + pattern.length()) - 'A' + 1)) % p;
			}
			
			//negative hash value
			if (txtHash < 0)
			{
                             txtHash += p;
                         }
			
		}
		return indices;
	}
	
	private boolean match(String text, String pattern)
	{	
		boolean flag = true;
		for (int i = 0; i < pattern.length(); i++)
		{
			if(text.charAt(i) != pattern.charAt(i))
			{
				flag = false;
				break;
			}
		}
		
		return flag;
	}

	public static void main(String[] args)
	{
		RabinKarpRollHash soln = new RabinKarpRollHash();
		List<Integer> ans = soln.rollHash("ecda", "ecdadecdacde");
		System.out.println(ans);
	}
}

This is the code that i wrote to my understanding level, any corrections are welcomed

Blade2Cruzor · 2024-12-12T12:39:18Z

package gfg;

import java.util.ArrayList;

public class RabinKarpRollHash
{
	
	private ArrayList<Integer> rollHash(String pattern, String text)
	{
		ArrayList<Integer> indices = new ArrayList<Integer>();
		int patHash = 0;
		int txtHash = 0;
		
		for (char c : pattern.toCharArray())
		{
			patHash += c;
		}
		
		for (int i = 0; i < pattern.length(); i++)
		{
			txtHash += text.charAt(i);
		}

		for (int i = 0; i <= text.length() - pattern.length(); i++)
		{
			//declaration
			String textToCompare = text.substring(i, i + pattern.length());
			
			//condition for matched pattern
			if (patHash == txtHash && textToCompare.equals(pattern))
			{
				indices.add(i + 1);			
			}
			
			//calculate hash till last pattern string
			if(i < text.length() - pattern.length())
			{
				txtHash = txtHash - text.charAt(i) + text.charAt(i + pattern.length());
			}
			
		}
		return indices;
	}		

	public static void main(String[] args)
	{
		RabinKarpRollHash soln = new RabinKarpRollHash();
		ArrayList<Integer> ans = soln.rollHash("egibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebd", "egibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdibegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdcfegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdiiedegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdeghegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebddgddfegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdaedggagegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdadeaaheabidegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdbbegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdhaegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebddegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdeaaeaegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdhegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdiacegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdhegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebddegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdcegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdaihhccegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdfegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdiegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdaegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdccaegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdbegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdhicgggiegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdiagegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdabfgdfhbhegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdedegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdheaegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdgegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdgdcegibbbdbgdiedabcbidgdiicahagehfihbiedaebchicaaiebhibhcaihbahfedaadacegggcchihgbfgccficffdgaeiebdaadb");
		System.out.print(ans);
	}
}

I tried this without hash

KarthikVarma19 · 2025-03-12T13:27:44Z

import java.util.ArrayList;
import java.util.Scanner;

public class rabinKarp {
public static void main(String args[]) {
Scanner sc = new Scanner(System.in);
System.out.print("Enter the string1:- ");
String str1 = sc.nextLine();
System.out.print("Enter the string2:- ");
String str2 = sc.nextLine();
sc.close();
if (str2.length() > str1.length()) {
return;
}
rabin(str1, str2);
}

private static final int BASE = 256;
private static final long PRIME = 10000007;

private static void rabin(String txt, String pat) {
    // Precomputing BASE^(M-1) When Deleting the First Character It is useful
    long h = 1;
    for (int i = 0; i < pat.length() - 1; i++) {
        h = (h * BASE) % PRIME;
    }

    ArrayList<Integer> indexes = new ArrayList<>();

    long patHash = calculateHash(pat);
    long windowHash = calculateHash(txt.substring(0, pat.length()));

    for (int i = 0; i <= txt.length() - pat.length(); i++) {
        
        if (windowHash == patHash) {
            indexes.add(i);
        }
        
        System.out.println(patHash + " " + windowHash);
        int ascciOld = txt.charAt(i);

        // Remove first character from hash
       // ( windowHash - (1 * h) % prime + prime ) prime
        windowHash = (windowHash - (ascciOld * h) % PRIME + PRIME) % PRIME;

        if (i + pat.length() < txt.length()) {
            int ascciNew = txt.charAt(i + pat.length());
            // (windowHash * Base + assciNew) % prime
            windowHash = (windowHash * BASE + ascciNew) % PRIME;
        }

    }

    System.out.println(indexes);
}

private static long calculateHash(String str) {
    long hash = 0;
    for (int i = 0; i < str.length(); i++) {
        hash = (hash * BASE + str.charAt(i)) % PRIME;
    }
    return hash;
}

}

	/* 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

SuryaPratapK/Rabin_Karp_Algo_Rolling_Hash

9540621011 commented Mar 9, 2021

Uh oh!

deekshith39 commented Mar 26, 2021

Uh oh!

adityarawat1337x commented May 20, 2021

Uh oh!

ShreyBansal22 commented Jul 6, 2021

Uh oh!

rohit2sAahu commented Jul 20, 2021

Uh oh!

SushantPatial commented Aug 12, 2021 •

edited

Loading

Uh oh!

akshat-fsociety commented Sep 2, 2021

Uh oh!

babluparihar commented Oct 30, 2021

Uh oh!

mohit421 commented Sep 15, 2022

Uh oh!

xsanket commented Jan 18, 2024

Uh oh!

Blade2Cruzor commented Dec 12, 2024 •

edited

Loading

Uh oh!

Blade2Cruzor commented Dec 12, 2024

Uh oh!

KarthikVarma19 commented Mar 12, 2025

Uh oh!

SuryaPratapK/Rabin_Karp_Algo_Rolling_Hash

9540621011 commented Mar 9, 2021

Uh oh!

deekshith39 commented Mar 26, 2021

Uh oh!

adityarawat1337x commented May 20, 2021

Uh oh!

ShreyBansal22 commented Jul 6, 2021

Uh oh!

rohit2sAahu commented Jul 20, 2021

Uh oh!

SushantPatial commented Aug 12, 2021 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

akshat-fsociety commented Sep 2, 2021

Uh oh!

babluparihar commented Oct 30, 2021

Uh oh!

mohit421 commented Sep 15, 2022

Uh oh!

xsanket commented Jan 18, 2024

Uh oh!

Blade2Cruzor commented Dec 12, 2024 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Uh oh!

Blade2Cruzor commented Dec 12, 2024

Uh oh!

KarthikVarma19 commented Mar 12, 2025

Uh oh!

SushantPatial commented Aug 12, 2021 •

edited

Loading

Blade2Cruzor commented Dec 12, 2024 •

edited

Loading