关于 hash 的问题
  • 板块学术版
  • 楼主_sh1kong_
  • 当前回复7
  • 已保存回复7
  • 发布时间2023/7/4 21:27
  • 上次更新2023/11/3 11:35:15
查看原帖
关于 hash 的问题
823773
_sh1kong_楼主2023/7/4 21:27

RT,众所周知 KMPKMP算法在一个主串中查找一个子串出现的位置这类问题中,可以达到O(N+M)O(N + M)的效果。

但是,我们难道不可以在主串中遍历一个左端点,右端点r=l+m−1r = l + m - 1 (( mm 为子串的长度 )),那么知道了左右端点,我们便可以用 hashhash O(1)O(1)的复杂度判断是否相等,这样整个算法的复杂度几乎为 O(N)O(N)。

思路是否正确?不正确的话,请给出反例 qwqqwq

2023/7/4 21:27
加载中...