KMP algorithm pattern calculation issue

Question

Here is my code and test case. My question is, it seems the value of KMP pattern will never increase, since in last iteration, we checked pattern[i] != pattern[j], and in current round if (j == -1) or (pattern[j] == pattern[i]) cannot be true unless j == -1?

def findPattern(pattern):

   j = -1
   next = [-1] * len(pattern)
   i = 0 # next[0] is always -1, by KMP definition

   while (i+1 < len(pattern)):
       if (j == -1) or (pattern[j] == pattern[i]):
           i += 1
           j += 1
           if pattern[i] != pattern[j]:
               next[i] = j
           else:
               next[i] = next[j]
       else:
           j = next[j]

   return next

if __name__ == "__main__":

   # print findPattern("aaaab")
   print findPattern("abaabc")

thanks in advance, Lin

I am getting correct output when using KMP with your findPattern(pattern) function, could you post what you expect? Also, it seems that codereview.stackexchange.com/questions/109281/… and codereview.stackexchange.com/questions/107909/… verified that you are getting indeed the correct output and improved your code. — jermenkoo
– jermenkoo, Commented Nov 18, 2015 at 2:42
@jermenkoo, thanks for the comments. I checked again and you are correct. I just want to confirm, when condition of "pattern[i] != pattern[j]" is triggered in last loop iteration, in the next loop iteration, condition "pattern[j] == pattern[i]" could never be true and its related next pattern value will always decrease since j=next[j] is trigger, correct? Thanks. — Lin Ma
– Lin Ma, Commented Nov 18, 2015 at 8:25

discover · Accepted Answer · 2015-11-18 03:29:19Z

1

You have already increased i and j, so you are actually checking pattern[i+1] != pattern[j+1] after if (j == -1) or (pattern[j] == pattern[i])

answered Nov 18, 2015 at 3:29

discover

463 bronze badges

Sign up to request clarification or add additional context in comments.

8 Comments

Lin Ma Over a year ago

Thanks discover, I just want to confirm my understanding is correct, when condition of "pattern[i] != pattern[j]" is triggered in last loop iteration, in the next loop iteration, condition "pattern[j] == pattern[i]" could never be true and its related next pattern value will always decrease since j=next[j] is trigger, correct? Thanks.

discover Over a year ago

@LinMa And your code is wrong. findPattern("abaabc") should return [-1, -1, 0, 0, 1, -1].

Lin Ma Over a year ago

Thanks discover for confirming my understanding is correct.

discover Over a year ago

I think your understanding of kmp is different from mine. My return is -1, which means that if 'ab' prefix matches in current positions (not means that 'ab' does not match) but the character in the next positons do not match, then we move the current postion of pattern string to -1 (yes, we know the character in current position is 'b', does not match the 'a' in postion 0) and try to match the next charater in next step, which means we should try match the 'a' in position 0 of pattern string.

discover Over a year ago

Hi, Lin Ma. You can test your code by solving the problem: poj.org/problem?id=3461

|

Collectives™ on Stack Overflow

KMP algorithm pattern calculation issue

1 Answer 1

8 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

8 Comments

Your Answer

Sign up or log in

Post as a guest

Related