Problem Statement
Which concept does the Rabin–Karp algorithm use for pattern matching?
Explanation
Rabin–Karp uses rolling hash to compare hash values of pattern and text substrings. If hash values match, it verifies the substring directly. This approach improves average performance for multiple pattern matches.
Code Solution
SolutionRead Only
int search(String text,String pat){
int n=text.length(),m=pat.length(),q=101;
int p=0,t=0,h=1,d=256;
for(int i=0;i<m-1;i++) h=(h*d)%q;
for(int i=0;i<m;i++){ p=(d*p+pat.charAt(i))%q; t=(d*t+text.charAt(i))%q; }
for(int i=0;i<=n-m;i++){
if(p==t){ int j; for(j=0;j<m;j++) if(text.charAt(i+j)!=pat.charAt(j)) break;
if(j==m) return i; }
if(i<n-m){ t=(d*(t-text.charAt(i)*h)+text.charAt(i+m))%q; if(t<0)t+=q; }
}
return -1; }Practice Sets
This question appears in the following practice sets:
