---
title: "字符串哈希"
created: 2025-11-28
tags:
  - 算法
---

# 字符串哈希

## 题目 [字符串哈希](https://www.acwing.com/problem/content/843/)

![[image-0ec34f24.png]]

## 思路分析

![[image-7e2b1cc1.png]]

使用这种方法就假定了人品足够好，不出现冲突

## 代码实现

```cpp
#include<bits/stdc++.h>
using namespace std;

typedef unsigned long long ULL;//越界等同于模2^64
const int N=100010,P=131;//P取131或13331不易碰撞
char str[N];
ULL h[N],p[N];

ULL get(int l,int r)
{
    //1~r减去1~l-1 但是要左移 移多少 r-l+1位 即乘上p^r-l+1
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    int n,m;
    cin>>n>>m;
    cin>>str+1;//不要把某一位映射成P进制0 A如果是0 AA也是0 冲突 所以从1开始

    p[0]=1;//p^0=1
    for(int i=1;i<=n;i++)
    {
        h[i]=h[i-1]*P+str[i];//构造“字符串前缀和” 左移一位加当前位的ascii值（+x*p^0 即x本身）
        p[i]=p[i-1]*P;//等价于p^0 p^1 p^2 p^3
    }

    while(m--)
    {
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;

        if(get(l1,r1)==get(l2,r2))
            puts("Yes");
        else
            puts("No");
    }

    return 0;
}
```

## 同类题型

## 视频讲解

---
⬅️ [[模拟散列表|模拟散列表]] 🏠 [[00-听课板子]]