Pattern_searching is an important problem in computer science. When we do search for a string in a notepad/word file or browser or database, pattern-searching algorithms are used to show the search results.
- The basic idea behind KMP’s algorithm is: whenever we detect a mismatch (after some matches), we already know some of the characters in the text of the next window. We take advantage of this information to avoid matching the characters that we know will anyway match.
- it’s an optimization for naive string pattern searching
- Tc: O(m+n)
- get first string, get last string n length of m
- is the suffic also a prefix
- there is a wierd way of creating num array based on string vals, like we keep two pointers and if there is a char match we increment corresponding index value as well as move first pointer by 1.
- if after few matching chars, unmatching char is found then j jumps back
- looks like a prefix suffix magic
- The ls array is keeping a track of last matching string Location
- 2 in array location is saying there is a suffix which is also a prefix
- array values for string Shivaji?