Кнута-Морриса-Пратта Алгоритм Поиска Питон 2


Я попытался вновь реализовать алгоритм. Просто нужен кто-то, чтобы проверить мою работу. Я надеюсь я ничего не пропустил, но в последнее время моей многолетней работы часов были довольно неприхотлива в моем мозгу так что я, честно говоря, не удивлюсь, если я что-то напутал.

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


142
1
задан 12 апреля 2018 в 12:04 Источник Поделиться
Комментарии
1 ответ

именования

Имя переменной является частью документации кода. Попробуйте использовать осмысленные имена, что не тень встроенные модули.


  • ЗСВ: суб (как в str.find)

  • ул.: вся

  • Вт: sub_index

  • с: whole_index

Генераторы

Вместо того, чтобы заполнять список и возвращает список, я предпочитаю работать с генераторами почти в каждом случае. Если получать результат в коллекции, потом очень удобно

Зацикливание

в KMP_table вы по сути цикл по индексу (position). Вместо петли на word и enumerate

мелкие вещи


  • candidate += (position - candidate) по сути candidate = position

  • lenWrd используется дважды, lenStr используется один раз, так что они могут быть встроенные

результат

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)

2
ответ дан 12 апреля 2018 в 01:04 Источник Поделиться