Given a text txt[0…n-1] and a pattern pat[0…m-1], write a function search(char pat, char txt) that prints all occurrences of pat in txt. You may assume that n > m
Input: txt = "AABAACAADAABAABA" pat = "AABA" Output: Pattern found at index 0 Pattern found at index 9 Pattern found at index 12
Initially, we discuss the strategy which is checking the pattern by moving window one by one, but without checking all characters for all cases (finding the hash value).
When the hash value is matched, then only it tries to check each character.
Pseudo Code: -
for i := 0 to (lenStr - patLen), do if patHash = strHash, then for charIndex := 0 to patLen -1, do if text[i+charIndex] ≠ pattern[charIndex], then break the loop if charIndex = patLen, then print the location i as pattern found at i position. if i < (lenStr - patLen), then strHash := (maxChar*(strHash – text[i]*h)+text[i+patLen]) mod prime, then if strHash < 0, then strHash := strHash + prime