current community

your communities

more stack exchange communities

company blog
Stack Exchange Inbox Reputation and Badges
tour help
Sign up ×
Code Review Stack Exchange is a question and answer site for peer programmer code reviews. It's 100% free, no registration required.
up vote 1 down vote favorite

Write the implementation for generating pattern part, and did some testing, seems good to me. But not sure if any functional bugs? If anyone find a functional bug, appreciate for the insights.

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")
share|improve this question

migrated from stackoverflow.com Oct 30 at 16:15

This question came from our site for professional and enthusiast programmers.
1  
It's not a functional bug, but next is the name of a builtin function in Python, and it's potentially confusing to reuse that for your own variable name, as other people will expect it to do something else - and if you need the real function at some point, it may cause problems. – TessellatingHeckler Oct 18 at 0:57
    
@TessellatingHeckler, nice catch and learn from you. Any functional issues you found? :) – Lin Ma Oct 18 at 0:57
1  
I am not very familiar with KMP; I don't know enough to say about functional bugs, sorry. – TessellatingHeckler Oct 18 at 1:04
    
@TessellatingHeckler, thanks all the same, no worries. Let us see if anyone have any good ideas. – Lin Ma Oct 18 at 1:09

1 Answer 1

up vote 2 down vote accepted

You can see your implementation is wrong by examining the simplest case, a pattern P consisted of a repeated single character: "AAAAA". At every point of the failure function, the length of the largest proper prefix of P which is also a proper suffix of P is ever-increasing: [-1, 0, 1, 2, 3] - however your implementation computes [-1, -1, -1, -1, -1].

Translating the pseudocode in the Wikipedia entry into Python gives us:

def kmp_table(pattern):
    if len(pattern) == 0:
        return None

    ff = [0] * len(pattern) # FF for failure function
    ff[0] = -1
    pos = 2
    cnd = 0

    while pos < len(pattern):
        if pattern[pos - 1] == pattern[cnd]:
            cnd += 1
            ff[pos] = cnd
            pos += 1
        elif cnd > 0:
            cnd = ff[cnd]
        else:
            ff[pos] = 0
            pos += 1

    return ff
share|improve this answer
    
I think -1 is expected since if 'A' is not matched, it means other 'A's cannot be matched, so I return -1. Please feel free to correct me if I am wrong. :) – Lin Ma Oct 20 at 3:10
    
Remember, when you have a mismatch, you also have a partial match, which is a proper prefix, and which you don't need to re-check because you already did so. That means on a mismatch you point the index on FF wherever FF[index] says (by definition), hence it can't be -1 for all positions of "AAAAA". Then, the beginning of the current match m must be: m + index - ff[index], and for the reason you mentioned (if you encounter a "B" you can only slide the pattern past the "B") ff[index] cannot be -1 anywhere but the first place. – Michael Foukarakis Oct 20 at 5:17
    
Hi Michael, suppose we are using pattern "AAAAA" to match "AB......", the 2nd element does not match A, and also since in pattern the first element is equal to the 2nd element, so if we compare to the first element again, it does not match. So I write -1 here to illustrate if the 2nd element does not match (and the first element match), there is no match for current position, is the logic correct? If so, in your case, if B does not match, what is the next element in pattern string to match for? Thanks. – Lin Ma Oct 20 at 7:53
    
Hi Michael, when we met with -1 during match, we will move forward one position in source string. – Lin Ma Oct 20 at 7:54
    
Hi Michael, if you could comment on my above question, it will be great. Have a good weekend. :) – Lin Ma Oct 25 at 1:49

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.