×

# Can I use lps array of kmp algorithm for string matching using Z algorithm's string concatenation technique?

 0 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 893●2●11●34 accept rate: 10%

 0 Your idea is correct. lps[i] is equal to the longest suffix of i-th 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 2★akali 16●2 accept rate: 0%
 toggle preview community wiki:
Preview

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported
• mathemetical formulas in Latex between \$ symbol

Question tags:

×66
×41

question asked: 24 Oct '16, 19:49

question was seen: 741 times

last updated: 25 Oct '16, 00:05