Ram*_*rar 4 c++ string algorithm hash anagram
我正在尝试从字符串text中找到子字符串,该字符串是字符串的字谜pattern.
我的问题: 请问拉宾,卡普算法进行调整,以这个目的是什么？还是有更好的算法？
我尝试过一种蛮力算法,在我的情况下不起作用,因为文本和模式每个都可以达到一百万个字符.
更新:我听说有一种使用O(1)空间的最坏情况O(n 2)算法.有谁知道这个算法是什么？
更新2:作为参考,这里是Rabin-Karp算法的伪代码:
function RabinKarp(string s[1..n], string sub[1..m])
hsub := hash(sub[1..m]); hs := hash(s[1..m])
for i from 1 to n-m+1
if hs = hsub
if s[i..i+m-1] = sub
return i
hs := hash(s[i+1..i+m])
return not found
这使用滚动散列函数来允许在O(1)中计算新散列,因此在最坏的情况下整体搜索是O(nm),但是在最好的情况下具有良好的散列函数是O(m + n) .few collisions在搜索字符串的字谜时会产生滚动哈希函数吗？
计算模式的散列,该散列不依赖于模式中字母的顺序(例如,使用每个字母的字符代码的总和).然后以"滚动"方式将相同的哈希函数应用于文本,如Rabin-Karp.如果散列匹配,则需要对文本中的当前窗口执行模式的完整测试,因为散列也可能与其他值发生冲突.
通过将字母表中的每个符号与素数相关联,然后将这些素数的乘积计算为哈希码,您将获得更少的冲突.
但是,如果你想要计算这样的运行产品,有一些数学技巧可以帮助你:每次你步进窗口时,将运行的哈希码乘以符号代码的乘法逆.离开窗口,然后乘以进入窗口的符号的代码.
例如,假设您将字母'a' - 'z'的散列计算为无符号的64位值.使用这样的表格:
symbol | code | code-1 -------+------+--------------------- a | 3 | 12297829382473034411 b | 5 | 14757395258967641293 c | 7 | 7905747460161236407 d | 11 | 3353953467947191203 e | 13 | 5675921253449092805 ... z | 103 | 15760325033848937303
n的乘法逆是在乘以n时产生1的数,以某个数为模.这里的模数是2 64,因为你使用的是64位数字.5 * 14757395258967641293例如,应该是1.这是有效的,因为你只是乘以GF(2 64).
计算第一个素数列表很容易,您的平台应该有一个库来有效地计算这些数字的乘法逆.
用数字3开始编码,因为2是一个整数大小的共同素数(在你正在处理的任何处理器上的幂为2),并且不能被反转.
一种选择是保持一个滑动窗口,其中包含窗口中包含的字母的直方图.如果该直方图最终等于应该找到其字谜的字符串的字符直方图,那么您知道您正在查看的是匹配并可以输出它.如果没有,你知道你拥有的东西不可能是匹配的.
更具体地说,创建一个关联数组从字符到其频率的映射.如果要搜索字符串P的字谜,请阅读第一个| P | 从文本字符串T到A的字符并适当地构建直方图.您可以将窗口向前滑动一步,并通过递减与窗口中第一个字符关联的频率,然后递增与滑入窗口的新字符相关联的频率,在O(1)关联数组操作中更新A.
如果当前窗口和模式窗口的直方图非常不同,那么您应该能够相当快地比较它们.具体来说,假设您的字母表是Σ.在最坏的情况下,比较两个直方图会花费时间O(|Σ|),因为您必须使用参考直方图检查直方图A中的每个字符/频率对.但是,在最好的情况下,您会立即找到导致A与参考直方图不匹配的字符,因此您不需要查看整个字符.
理论上,这种方法的最坏情况运行时是O(| T ||Σ| + | P |),因为你必须做O(n)工作来构建初始直方图,然后必须做最坏情况的Σ工作T中的每个字符.但是,我希望在实践中这可能要快得多.
希望这可以帮助!