Knuth-Morris-Pratt搜索算法2 Python
Knuth-Morris-Pratt搜索算法2 Python
提问于 2018-04-12 12:59:12
我试着用再一次来实现算法。只是需要有人检查一下我的工作。我希望我没有错过任何东西，但我的长时间工作最近一直对我的大脑相当劳累，所以老实说，我不会感到惊讶，如果我搞砸了。
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回答 1
Code Review用户
回答已采纳
发布于 2018-04-12 13:59:05
命名
变量的名称是代码文档的一部分。尽量使用有意义的名字，不要隐藏内置的内容。
- wrd: sub (在
str.find中) - 斯特尔:整个
- w: sub_index
- s: whole_index
发生器
与其填写列表并返回列表，我更喜欢在几乎每种情况下都使用生成器。如果事后在集合中获得结果非常简单
循环
在KMP_table中，本质上是按索引循环(position)。相反，循环遍历word和enumerate
小事物
candidate += (position - candidate)本质上是candidate = positionlenWrd使用两次，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)
页面原文内容由Code Review提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接：
https://codereview.stackexchange.com/questions/191872
复制相关文章
相似问题
腾讯云开发者
