Rabin Karp - Pattern Searching

PHOTO EMBED

Tue Feb 08 2022 11:57:07 GMT+0000 (Coordinated Universal Time)

Saved by @Uttam #java #gfg #geeksforgeeks #lecture #string #patternsearching #rabinkarp

import java.util.*;
import java.io.*;
  
class GFG { 
    static final int d=256;
    static final int q=101;   
    static void RBSearch(String pat,String txt,int M, int N)
    {
        //Compute (d^(M-1))%q
        int h=1;
        for(int i=1;i<=M-1;i++)
            h=(h*d)%q;
        
        //Compute p and to
        int p=0,t=0;
        for(int i=0;i<M;i++){
            p=(p*d+pat.charAt(i))%q;
            t=(t*d+txt.charAt(i))%q;
        }
        
        for(int i=0;i<=(N-M);i++){
           //Check for hit
           if(p==t){
               boolean flag=true;
               for(int j=0;j<M;j++)
                    if(txt.charAt(i+j)!=pat.charAt(j)){flag=false;break;}
                if(flag==true)System.out.print(i+" ");
           }
           //Compute ti+1 using ti
           if(i<N-M){
               t=((d*(t-txt.charAt(i)*h))+txt.charAt(i+M))%q;
            if(t<0)t=t+q;
           }
        }
        
    }
  
    public static void main(String args[]) 
    {   String txt = "GEEKS FOR GEEKS";String pat="GEEK";
        System.out.print("All index numbers where pattern found: ");
        RBSearch(pat,txt,4,15);  
    } 
} 
content_copyCOPY

Rabin Karp Algorithm Input : -------- Text = "GEEKS FOR GEEKS" Pattern ="GEEK" Output: --------- All index numbers where pattern found: 0 10