0
\$\begingroup\$

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")
\$\endgroup\$

migrated from stackoverflow.com Oct 30 '15 at 16:15

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ 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. \$\endgroup\$ – TessellatingHeckler Oct 18 '15 at 0:57
  • \$\begingroup\$ @TessellatingHeckler, nice catch and learn from you. Any functional issues you found? :) \$\endgroup\$ – Lin Ma Oct 18 '15 at 0:57
  • 1
    \$\begingroup\$ I am not very familiar with KMP; I don't know enough to say about functional bugs, sorry. \$\endgroup\$ – TessellatingHeckler Oct 18 '15 at 1:04
  • \$\begingroup\$ @TessellatingHeckler, thanks all the same, no worries. Let us see if anyone have any good ideas. \$\endgroup\$ – Lin Ma Oct 18 '15 at 1:09
2
\$\begingroup\$

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
\$\endgroup\$
  • \$\begingroup\$ 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. :) \$\endgroup\$ – Lin Ma Oct 20 '15 at 3:10
  • \$\begingroup\$ 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. \$\endgroup\$ – Michael Foukarakis Oct 20 '15 at 5:17
  • \$\begingroup\$ 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. \$\endgroup\$ – Lin Ma Oct 20 '15 at 7:53
  • \$\begingroup\$ Hi Michael, when we met with -1 during match, we will move forward one position in source string. \$\endgroup\$ – Lin Ma Oct 20 '15 at 7:54
  • \$\begingroup\$ Hi Michael, if you could comment on my above question, it will be great. Have a good weekend. :) \$\endgroup\$ – Lin Ma Oct 25 '15 at 1:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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