Наивная реализация алгоритма сопоставления с образцом Карпа-Рабина

У меня возникли проблемы с реализацией наивной версии шаблона Карпа-Рабина маршер; Я не получаю ожидаемого результата. Вот мой пример;

string='today is a good day'
sub='good'

Я хотел бы найти хороший шаблон в строке выше.

def kapr(n,m):
    for i in range(len(n)-len(m)+1):
        for j in range(len(m)):
            if n[i+j-1]!=m[j]:
                continue
        return i
    return not found

Print (kapr(string, sub))

Output=0 Ожидаемый output=11 должен соответствовать смещению good в строке.

Спасибо за вашу помощь.


python rabin-karp
person user2274879    schedule 26.09.2017    source источник

Ответы (1)


arrow_upward
1
arrow_downward

Вы хотите break вместо continue. Продолжить перейдет к следующей итерации внутреннего цикла, а break выйдет из внутреннего цикла. Кроме того, вы не переходите непосредственно к следующей итерации внешнего цикла с помощью break, поэтому вы нажмете оператор return i. Чтобы этого не происходило, вы можете использовать ветку for/else.

E.g.

for j in range(len(m)):
    if n[i+j-1]!=m[j]:
        break
else:
    return i

Это будет только return i, если внутренний цикл завершится нормально.

Индекс, который он возвращает, также не имеет нулевого индекса, поэтому с приведенными выше изменениями он вернет 12. Должно быть просто обновить, если вы хотите, чтобы он был нулевым индексом!

person Rach Sharp    schedule 26.09.2017