Rabin-Karp Algorithm
String Matching: A string (say txt) and a pattern( smaller string say pat) are given and ask for finding the position of pat in txt. Let the length of txt = n and length of pat is m. Method 1: Naive Approach Traverse string txt from 0 to (n-m+1) and in every round check if part of txt match with pat character by character. The time complexity of this algorithm will be O(m*n) . Method 2: Rabin-Karp algorithm In this method, we use a hash function to hash pat and hash part of txt of size m and apply the rolling hash method and is the hash function of part of txt match with pat then check pat and txt character by character. Time Complexity: O(n-m+1) Average Time Complexity: O(n-m+1) Worst eg: txt : a a a a a b and pat: a a b Let the hashing begin with 1 and end with 26 as: hash(a): 1 hash(b): 2 ----------- ----------- hash(z): 26 hash(a a a): 1+1+1=3 hash(a a b): 1+1+2=4