AcWing 841. 字符串哈希python3    原题链接    简单

作者： 作者的头像   xanxus1111 ,  2020-05-10 16:48:01 ,  所有人可见 ,  阅读 1073

6


4 

# p 取 131 或 13331 q 取 2的64次方 99.99%不会冲突 （经验）
# h[i] = h[i-1] * p + str[i]
# L-R的hash值 = h[R] - h[L] * p**(R-L+1)

def get(l,r):
    return  (h[r] - h[l-1] * p[r-l+1] ) % mod

if __name__ == "__main__":
    mod = 998244353   #取模是因为C++会自动溢出相当于取模了 python不会 所以需要手动取模
                        #ps 998244353=7*17*2**23+1，一个质数 UOJ专用NTT模数
    P = 131

    n,m = map(int,input().split())
    s = input()

    h, p,  = [0]*(n+1), [1]*(n+1),   # p[i] 数组里面储存的是 p 的 i 次方

    for i in range(1,n+1):
        p[i] = ( p[i-1] * P ) % mod
        h[i] = ( h[i-1] * P + ord(s[i-1]) ) % mod

    for i in range(m):

        l1,r1,l2,r2 = map(int,input().split())

        if get(l1,r1) == get(l2,r2): print('Yes')
        else:print('No')

6 评论

用户头像
Maxmin   2022-01-26 15:58         踩      回复

我想请教一下，为什么get函数中return也要取模？h中和p中的值不是不会很大了吗?那么取模是不是没必要？（但是去掉以后，又发生错误）

用户头像
xanxus1111   2022-01-27 21:46         踩      回复

get 函数中有乘法，你打印一下结果就知道了。也会很大

用户头像
Maxmin   2022-01-27 22:27    回复了 xanxus1111 的评论         踩      回复

好的，谢谢你！

用户头像
番茄酱   2020-05-10 20:40         踩      回复

emmm，y总没取模是因为c++对unsigned long long溢出自动取模了，python它不会这样啊，所以你的哈希值越算越大，然后就超时了。

mod = 998244353

def get(l,r):
    return (h[r] - h[l-1] * p[r-l+1]) % mod;

if __name__ == "__main__":

    P = 131

    n,m = map(int,input().split())
    s = input()

    h, p,  = [0]*(n+1), [1]*(n+1),   # p[i] 数组里面储存的是 p 的 i 次方 h[i] 是字符串0-i的hash值

    for i in range(1,n+1):
        p[i] = p[i-1] * P % mod
        h[i] = (h[i-1] * P + ord(s[i-1])) % mod

    for i in range(m):

        l1,r1,l2,r2 = map(int,input().split())

        if get(l1,r1) == get(l2,r2): print('Yes')
        else:print('No')
用户头像
番茄酱   2020-05-10 20:41         踩      回复

取模就能AC啦

用户头像
xanxus1111   2020-05-11 06:26    回复了 番茄酱 的评论         踩      回复

谢谢大佬！ 我昨天也想到是不是因为后面10000次方的原因来着 没想好模取多少好 感谢感谢