// image taken in gallery
Naive String matching : GIven a text → txt[]= AABAACAADAABAABA txt [0……………n-1] where n = 16 {in our example} pattern [0…..m-1] where m = 4 with naive string matching algo the task is to print the positions from text where the pattern exists the working principle of naive string matching as followed : it compares each and every character from pattern with given txt if the match is not found then it slides the window to the next character in the txt
txt[] = AABAACAADAABAABA pattern[] = AABA
draw backs manually checking each and every character is a time consuming process so we RABIN - KARP algorithm to speed up pattern matching using hashing techniques in this method strings are converted into numerical and its hash code is computed the function or process use to generate the hash code is known as hash function
Converting characters into Strings is nothing but considering ASCII code for each and every character a → 1 b → 2 c → 3 d → 4 e → 5 f → 6 g → 7 h→ 8 i → 9 j → 10
Reason behind spurious / invalid hit
if we take such a simple hash function then there is a collision with other substring which are having same hashcode though they are not pattern
so to avoid the number of spurious hits we need to take strong hash function
there are two techniques in rabin karp method
question
algorithm
KMP ALGORITHM
how to generate prefix and suffix array
