1
\$\begingroup\$

I tried again to implement the algorithm. Just need someone to check my work. I hope I didn't miss anything but my long work hours recently have been pretty taxing on my brain so I honestly wouldn't be surprised if I messed up somehow.

def KMP_table(wrd):
    #example: B A A B D C B A A A C A B -> [-1, 0, 0, -1, 1, 2, -1, 0, 0, 0, 4, 5, -1]
    table = []
    position, candidate = 0, 0
    while position < len(wrd):
        if wrd[candidate] == wrd[position]:
            table.append(-1)
            candidate += (position - candidate)
        elif wrd[position] == wrd[position - candidate] or candidate == 0:
            table.append(0)
        else:
            table.append(position - candidate)
        position += 1

    return table

def KMP_search(wrd, str):

    if not wrd or not str:
        raise ValueError("Empty lists")

    w, s = 0, 0
    lenWrd, lenStr = len(wrd), len(str)
    wrdPos = []

    table = KMP_table(wrd)
    while (s + lenWrd-1) < lenStr:
        if wrd[w] == str[w + s]:
            if w == lenWrd - 1:
               wrdPos.append(s)
               s += 1
               w = 0
            else:
                w += 1
        else:
            if table[w] > 0:
                s += (w - table[w])
            elif w == 0:
                s += 1
            else:
                s += w
            w = 0

    return wrdPos
\$\endgroup\$

1 Answer 1

Reset to default
2
\$\begingroup\$

naming

The name of a variable is part of the documentation of your code. Try to use meaningful names, that don't shadow built-ins.

  • wrd: sub (as in str.find)
  • str: whole
  • w: sub_index
  • s: whole_index

Generators

Instead of filling a list and returning that list, I prefer to work with generators in almost every case. If getting the result in a collection afterwards is very simple

Looping

in KMP_table you are essentially looping by index (position). Instead, loop over the word and enumerate

small things

  • candidate += (position - candidate) is essentially candidate = position
  • lenWrd is used twice, lenStr is used once, so they an be inline

result

def KMP_table(whole):
    # example: B A A B D C B A A A C A B -> [-1, 0, 0, -1, 1, 2, -1, 0, 0, 0, 4, 5, -1]
    candidate = 0
    for position, wrd_position in enumerate(whole):
        diff = position - candidate
        if whole[candidate] == wrd_position:
            yield -1
            candidate = position
        elif wrd_position == whole[diff] or candidate == 0:
            yield 0
        else:
            yield diff

def KMP_search(word, sub):
    if not word or not sub:
        raise ValueError("Empty lists")

    word_index, sub_index = 0, 0
    table = tuple(KMP_table(word))
    while (sub_index + len(word) - 1) < len(sub):
        if word[word_index] == sub[word_index + sub_index]:
            if word_index == len(word) - 1:
                yield sub_index
                sub_index += 1
                word_index = 0
            else:
                word_index += 1
        else:
            if table[word_index] > 0:
                sub_index += (word_index - table[word_index])
            elif word_index == 0:
                sub_index += 1
            else:
                sub_index += word_index
            word_index = 0

tuple(KMP_search('aba', 'aaababa'))

(2, 4)
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.