0

下图来自: 6.006-算法简介

在此处输入图像描述

在学习 MIT OCW 提供的 6.006-Introduction to algorithm 课程时,我遇到了 Rabin-Karp 算法。

谁能帮我理解为什么需要第一个 rs()==rt() ?如果使用了,那我们是不是也应该先通过蛮力检查字符串是否相等,然后继续前进?为什么在从 t[0] 进行散列然后尝试查找其他字符串匹配时我们不考虑字符串的相等性?

在图像中,rs() 用于哈希值,rs.skip[arg] 用于删除该字符串的第一个字符,假设它是'arg'</p>

4

1 回答 1

1

谁能帮我理解为什么rs()==rt()需要第一个?

我假设您的意思是范围循环之前的那个。如果字符串具有相同的长度,则范围循环将不会运行(空范围)。检查是必要的,以涵盖这种情况。

如果使用了,那我们是不是也应该先通过蛮力检查字符串是否相等,然后继续前进?

不知道你在这里的意思。...找到匹配的哈希后,发布的代码留空(带有)。让我们不要忘记,在这一点上,我们必须比较字符串以确认我们确实找到了匹配项。并且,是否继续搜索直到结束取决于(未显示)实现。

为什么在从 t[0] 进行散列然后尝试查找其他字符串匹配时我们不考虑字符串的相等性?

我真的不明白这部分。请注意,前两个循环用于填充输入字符串的滚动散列。然后检查我们此时是否有匹配,然后循环更新滚动哈希成对,然后比较它们。整个t检查,从头到尾。

于 2018-11-02T21:54:45.710 回答