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 

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

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

}