6
\$\begingroup\$

The Knuth–Morris–Pratt string search algorithm is described in the paper Fast Pattern Matching in Strings (SIAM J. Computing vol. 6 no. 2, June 1977). The initial step of the algorithm is to compute the next table, defined as follows:

The pattern-matching process will run efficiently if we have an auxiliary table that tells us exactly how far to slide the pattern, when we detect a mismatch at its jth character pattern[j]. Let next[j] be the character position in the pattern which should be checked next after such a mismatch, so that we are sliding the pattern j − next[j] places relative to the text.

The authors give the example of the pattern abcabcacab. If there is a mismatch at j=7:

abcabcacab
abcabca?

Then the pattern should be moved 3 places to the right and matching should continue with the 4th character of the pattern:

   abcabcacab
abcabca?

so next[7] = 4. In some cases we know we can skip the mismatched character entirely, for example if there is a mismatch at j=3:

abcabcacab
abc?

then the search should continue from the character after the mismatch:

    abcabcacab
abc?

These special cases are indicated by next[j] = −1.

(If you're reading the paper, note that the authors use indexes starting at 1 as in Fortran, but the Python convention is to use indexes starting at 0, so that's what I'm giving here.)

This is the code that computes the next table. Please review.

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")

Output:

[-1, -1, -1, -1, 3]
[-1, 0, -1, 1, 0, 2]
\$\endgroup\$
  • 3
    \$\begingroup\$ What is the expected output? What kind of patterns are you expecting to find? \$\endgroup\$ – holroy Oct 18 '15 at 6:14
  • 6
    \$\begingroup\$ Could you please write with words, what that output means? It's still a little unclear, and that makes it harder to provide a good review. \$\endgroup\$ – holroy Oct 18 '15 at 7:00
  • 1
    \$\begingroup\$ The algorithm linked is for detecting strings, but you said you're using it to create patterns? It's very hard to follow what your code is for in its current state. \$\endgroup\$ – SuperBiasedMan Oct 18 '15 at 11:28
  • 1
    \$\begingroup\$ I think that this is supposed to be the "table-building" part of the Knuth–Morris–Pratt algorithm. However, it doesn't build the same table as the algorithm given in Wikipedia, where it says the word ABCDABCD becomes the table [-1, 0, 0, 0, 0, 1, 2, 3], but findPattern("ABCDABCD") returns [-1, 0, 0, 0, -1, 0, 0, 0]. So either there's a bug in your code, or you are implementing some other table-building function and need to explain in more detail. \$\endgroup\$ – Gareth Rees Oct 18 '15 at 12:27
  • 4
    \$\begingroup\$ I have been reading the original Knuth–Morris–Pratt paper, from which I have learned that the Wikipedia article is seriously misleading — the algorithm it describes is not the same as the one in the KMP paper. The T table described in the Wikipedia article is the same as the f table in KMP — but the f table is just a step in the actual construction of the next table, which is what the KMP algorithm actually uses. So ignore what I said about failing to match the Wikipedia algorithm. \$\endgroup\$ – Gareth Rees Oct 20 '15 at 20:04
7
\$\begingroup\$

1. Review

  1. There's no docstring.

  2. There's no need for parentheses around conditions (Python is not C), so instead of:

    while (i+1 < len(pattern)):
    

    you can write:

    while i+1 < len(pattern):
    
  3. The loop while i+1 < len(pattern) calls the len function on each iteration, even though pattern has not changed. You could avoid this wasted call by caching len(pattern) in a local variable.

  4. The or operator has lower precedence than comparison operators, so instead of:

    if (j == -1) or (pattern[j] == pattern[i]):
    

    you can omit the parentheses:

    if j == -1 or pattern[j] == pattern[i]:
    
  5. When there's a choice about whether to test for equality or inequality, then I think it's usually clearer to test for equality, so I would write if pattern[i] == pattern[j] instead of if pattern[i] != pattern[j].

  6. There's a small inefficiency in your code. If the test j == -1 or pattern[j] == pattern[i] passes then you set j = next[j] and go round the while loop again. But the condition on the while loop is a condition on i, which has not changed, so you waste the test. It is better to go straight to the test on j, like this:

    m = len(pattern)
    while i + 1 < m
        while j > -1 and pattern[i] != pattern[j]:
            j = next[j]
        i += 1
        j += 1
        if pattern[i] == pattern[j]:
            next[i] = next[j]
        else:
            next[i] = j
    
  7. After making this change, i always increases by 1 on each iteration of the main loop, so we could use a for loop instead to make this clear.

2. Revised code

def kmp_table(pattern):
    """Compute the "next" table corresponding to pattern, for use in the
    Knuth-Morris-Pratt string search algorithm.

    """
    m = len(pattern)
    next = [-1] * m
    j = -1
    for i in range(1, m):
        while j > -1 and pattern[i-1] != pattern[j]:
            j = next[j]
        j += 1
        if pattern[i] != pattern[j]:
            next[i] = j
        else:
            next[i] = next[j]
    return next
\$\endgroup\$
  • \$\begingroup\$ Hi Gareth, accepted for your reply and appreciate for the learning. Wondering if any other functional bugs in your mind? For functional I mean the next[] is not generated correctly. :) \$\endgroup\$ – Lin Ma Oct 20 '15 at 22:17
  • 1
    \$\begingroup\$ The logic looks identical to that given in KMP, and it gives the same results as the examples in the paper. I haven't checked it beyond that. \$\endgroup\$ – Gareth Rees Oct 20 '15 at 22:30
  • \$\begingroup\$ Thanks Gareth, as long as you did not find any bugs, I am confident. :) \$\endgroup\$ – Lin Ma Oct 20 '15 at 22:40
  • \$\begingroup\$ Thanks for all the help Gareth, mark your reply as an answer. Have a good weekend. :) \$\endgroup\$ – Lin Ma Oct 25 '15 at 2:14
1
\$\begingroup\$

Effiiency time-complexity bug

while (i+1 < len(pattern)):

len(pattern) is evaluated at each iteration, even if it remains constant, this makes your time complexity n times slower, where n is len(pattern)

Use a variable to fix the bug:

pattern_length = len(pattern)

And:

while (i + 1 < pattern_length):
\$\endgroup\$
  • \$\begingroup\$ Thanks Caridorc, accepted for your reply and appreciate for the learning. Wondering if any other functional bugs in your mind? For functional I mean the next[] is not generated correctly. :) \$\endgroup\$ – Lin Ma Oct 20 '15 at 22:17
  • 5
    \$\begingroup\$ len is a constant time operation on strings and other builtin types, because each object stores its length. \$\endgroup\$ – Janne Karila Oct 21 '15 at 9:37
  • 1
    \$\begingroup\$ @JanneKarila Good I will delete this answer \$\endgroup\$ – Caridorc Oct 21 '15 at 12:55

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.