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

# 字符串哈希

## 分析

也是很简单但很精妙的算法

进制转换的内容 在复习过二进制后已经很熟悉了

这个字符串哈希就是仿用了P进制换10进制的方式实现的

P取经验值 131 所以可以记成是一个 131进制的数转变成10进制(把字符串当成一个131进制数）

![[image-c2f30b94.png]]

模上$2^{64}$其实就等价于一个8字节的东西溢出 对 直接用unsigned
long long存 将本该是问题的溢出巧妙转变成对$2^{64}$取模

然后我们就可以处理出所有字符串的一个哈希值

为了求某一段该怎么办

显然 这是前缀和问题

那么 我们可以用上面的方法 预处理出所有前缀字符串的哈希值的前缀和数组

要求某一段该怎么办

用s[r]-s[l]

发现并不对应 错了几位 所以得把前缀（l）部分 左移到与r 的高位匹配位置上去（后几位补0）

![[image-0dc90ec6.png]]

左移怎么做呢 左移一次就是\*p其实（这点在二进制里也讲的很清楚了）

左移两位就是$\*p^2$以此类推

那么要让l与r对齐 实际上是要左移r-l+1位

也就是我们要快速求到$p^{r-l+1}$

而每一位其实也是乘上一个p的n次方

所以我们完全也可以把p预处理出来

![[image-eb9e0407.png]]

构造前缀和数组就成了这样

![[image-19cdeb91.png]]

把上一个记录的值左移一位 然后加上当前位 就是截止当前位的哈希值

它用途比较广泛 不像kmp、trie那么具有鲜明特色（循环结、多次匹配、前缀匹配）

要说有非他不能解决的问题 那就是截取两段区间 问是否相等 这样的问题

它这种方式本质上是会有冲突的 只不过通过一些经验值 使得它能在大多数情况下不会发生冲突

用它解决问题的话可以不用想太多 直接当做是可行的 如果两串字符串最后的哈希值不一样就认为是不同的 直接水掉 所以它这种匹配方式很方便 可以解决大多数问题

代码实现也很简单

用ULL存 解决映射问题

在读入时就预处理好P的n次方和字符串哈希的前缀和

处理匹配问题只需要 用h[r]-h[l-1]\*p[r-l+1]即可 理解这个移位过程就好说

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

typedef unsigned long long ULL;
const int N=100010,P=131;
char str[N];
ULL h[N],p[N];
int n,m;

ULL get(ULL h[],int l,int r){
    return h[r]-h[l-1]*p[r-l+1];
}

int main()
{
    cin>>n>>m;
    cin>>str+1;
    p[0]=1;
    for(int i=1;i<=n;i++){
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
    }

    while(m--){
        int l1,r1,l2,r2;
        cin>>l1>>r1>>l2>>r2;
        if(get(h,l1,r1)==get(h,l2,r2))
            puts("Yes");
        else
            puts("No");
    }
    return 0;
}
```

## 题目：

字符串哈希
- [[兔子与兔子|兔子与兔子]]

- [[回文串的最大长度|回文串的最大长度]]
- [[后缀数组|后缀数组]]
- [[2-Learning/02-算法/03-刷题理模型/哈希表相关问题/矩阵|矩阵]]

更多题目：

- [最长公共子串](https://www.acwing.com/problem/content/description/3511/)
- [搜索字符串](https://www.acwing.com/problem/content/description/5223/)
- [三个朋友](https://www.acwing.com/problem/content/description/4187/)
- [前后缀字符串](https://www.acwing.com/problem/content/description/4186/)

---
⬅️ [[电话列表|电话列表]] 🏠 [[00-刷题理模型]] ➡️ [[兔子与兔子|兔子与兔子]]