RT,众所周知 KMPKMPKMP算法在一个主串中查找一个子串出现的位置这类问题中,可以达到O(N+M)O(N + M)O(N+M)的效果。
但是,我们难道不可以在主串中遍历一个左端点,右端点r=l+m−1r = l + m - 1r=l+m−1 ((( mmm 为子串的长度 ))),那么知道了左右端点,我们便可以用 hashhashhash O(1)O(1)O(1)的复杂度判断是否相等,这样整个算法的复杂度几乎为 O(N)O(N)O(N)。
思路是否正确?不正确的话,请给出反例 qwqqwqqwq