KMP algorithm finds Longest common prefix which is also a suffix. So like Z algorithm, if we concatenate pattern and text as pattern + '#' + text (where # is not in character set) and find lps[] of KMP and check how many lps[] elements are equal to pattern size like z algorithm, will we get the answer? e.g. text = aacabd and pat = ab concatenated string = ab#aacabd lps[] = 0 0 0 1 1 0 1 2 0 since one value is 2, it means the pattern is present in the text. Can anyone tell me if it is wrong for some test case? I am finding it a bit difficult to use KMP after finding LPS and finding it a bit hard to understand Z values. asked 24 Oct '16, 19:49

Your idea is correct. lps[i] is equal to the longest suffix of ith prefix, which is equal to prefix. And if one of the values of lps is equal to pattern's length it means that in text there is a substring which is equal to pattern, as substring is suffix of one prefixes. Sorry for my poor English. answered 25 Oct '16, 00:05
