Rabin_Karp_Algo_Rolling_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 

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