Powered by:NEFU AB-IN

Link

841. 字符串哈希

• 题意

  给定一个长度为 n 的字符串，再给定 m 个询问，每个询问包含四个整数 l1,r1,l2,r2，请你判断 [l1,r1] 和 [l2,r2] 这两个区间所包含的字符串子串是否完全相同。
  字符串中只包含大小写英文字母和数字。

• 思路

  字符串哈希板子题

  注意的点：

  • P为经验值，可以取131，也可以取13331
  • 对$2^{64}$进行取模
  • 别忘了对$p[0]$进行赋值为1，因为$p^0=1$
  • s = " " + s，字符串的第0位空出来
  • 区间和公式的理解: ABCDE 与 ABC 的前三个字符值是一样，只差两位，乘上 $P^2$, 把 ABC 变为 ABC00，再用 ABCDE - ABC00 得到 DE 的哈希值。

• 代码

  '''
  Author: NEFU AB-IN
  Date: 2022-02-12 16:07:23
  FilePath: \ACM\Acwing\841.py
  LastEditTime: 2022-02-12 16:12:41
  '''
  
  N = int(1e5 + 100)
  P, MOD = 131, 1 << 64
  
  h = [0] * N
  p = [0] * N
  
  p[0] = 1 #初始化
  
  
  def get(l, r):
      return (h[r] - h[l - 1] * p[r - l + 1]) % MOD
  
  
  if __name__ == "__main__":
      n, m = map(int, input().split())
      s = input()
  
      s = " " + s #空一位
  
      for i in range(1, n + 1):
          p[i] = p[i - 1] * P % MOD
          h[i] = (h[i - 1] * P + ord(s[i])) % 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")