This file has been truncated. show original
Pattern Searching Algorithm(PSA)? Algos searching a pattern inside given text.
txt = "AEEFD"; //len=n
pat = "EEF"; //len=m
Problem: Find indexes of pattern in txt.
Answer: pat[m] occurs in txt at indexes 1
Approach of rabin-karp?
- Works on Sliding window.
- Hash of pattern is compare with text window. size of text window = pattern size.
- if hashes does not match, text window is slided by one to right.
- New hash is not recalculated rather its calculated using:
oldhash + outgoing character + incoming character
- if hashes of text window and pattern matches, compare each letter in string, Since hash collisions can happen.