KMP Algorithm

'''
Why KMP works?
Text=    'ababx'
pattern= 'ababd'

At index 4, we get a mismatch. So we look at the pattern[0:i], i.e., "abab" Now we will look for longest prefix and suffix in that part ie pattern[0:i] so pattern[0:i] is 'abab' and Largest prefix and suffix in it is : 'ab' and then we can start matching again after the Longest prefix existed ie. 'ab' and the reason behind is:

pattern[0:i]-> "abab" is already matched in the main string, so the text currently ends with "abab".
Now, within this matched part, the suffix "ab" matches the prefix "ab" of the pattern[:i]
(i.e., the longest prefix which is also a suffix).

This means that a part of the text (ending before the mismatch index k) is already matching with the beginning of the pattern. Therefore, instead of restarting from the beginning of the pattern, we can continue matching from the position of this longest prefix, since it is already matched with the text.
'''