qjk*_*jkx 6 algorithm substring
我有一个字符串s,我想搜索最常出现在s中的长度为X的子字符串.允许重叠子串.
例如,如果s ="aoaoa"且X = 3,则算法应找到"aoa"(在s中出现2次).
是否存在在O(n)时间内执行此操作的算法？
您可以在O(n)时间内使用滚动哈希(假设良好的哈希分布)来执行此操作.一个简单的滚动哈希就是字符串中字符的xor,你可以使用2 xors从前一个子字符串哈希中逐步计算它.(有关比xor更好的滚动哈希值,请参阅Wikipedia条目.)使用O(n)时间内的滚动哈希计算n-x + 1子串的哈希值.如果没有碰撞,答案很清楚 - 如果碰撞发生,你需要做更多的工作.我的大脑很痛苦,试图弄清楚是否可以在O(n)时间内解决这个问题.
更新:
这是一个随机O(n)算法.您可以通过扫描哈希表来找到O(n)时间内的顶部哈希值(保持简单,假设没有联系).找到一个带有该哈希的X长度字符串(在哈希表中保留一条记录,或者只重做滚动哈希).然后使用O(n)字符串搜索算法在s中查找该字符串的所有出现.如果您发现与哈希表中记录的出现次数相同,则表示您已完成.
如果不是,那意味着您有哈希冲突.选择一个新的随机哈希函数,然后重试.如果你的散列函数有log(n)+1位并且是成对独立的[ Prob(h(s) == h(t)) < 1/2^{n+1} if s != t],则s散列中最频繁的x长度子串与s的<= n其他长度x子串的碰撞的概率最多为1/2.因此,如果存在冲突,请选择一个新的随机哈希函数并重试,在成功之前,您只需要一定数量的尝试.
现在我们只需要一个随机的成对独立滚动哈希算法.
UPDATE2:
实际上,你需要2log(n)位的散列来避免所有(n选择2)碰撞,因为任何碰撞都可能隐藏正确的答案.仍然可行,看起来像一般多项式除法的哈希应该做的伎俩.