search

matthewsamuel95 / ACM-ICPC-Algorithms

Algorithms used in Competitive Programming
2.07k stars 1.26k forks source link

KMP Algorithm for finding given pattern in text #756

Closed shreyansh08 closed 5 years ago

shreyansh08 commented 5 years ago

How to use lps[] to decide next positions (or to know a number of characters to be skipped)?

We start comparison of pat[j] with j = 0 with characters of current window of text.
We keep matching characters txt[i] and pat[j] and keep incrementing i and j while pat[j] and txt[i] keep matching.
When we see a mismatch
    We know that characters pat[0..j-1] match with txt[i-j+1…i-1] (Note that j starts with 0 and increment it only when there is a match).
    We also know (from above definition) that lps[j-1] is count of characters of pat[0…j-1] that are both proper prefix and suffix.
    From above two points, we can conclude that we do not need to match these lps[j-1] characters with txt[i-j…i-1] because we know that these characters will anyway match.
matthewsamuel95 commented 5 years ago

add the info posted here to a read me