堆
在计算机科学中，堆是一种专门的基于树的数据结构，它本质上是一个完全二叉树，可以使用链式结构的树来实现，但是由于堆一定是完全二叉树，通常使用数组来实现。
将根结点最大的堆叫做最大堆或大根堆，根结点最小的堆叫做最小堆或小根堆。我们统称为堆序性。
常见的堆有二叉堆、斐波那契堆等。习惯上，不加限定条件是，堆通常指二叉堆。
堆排序中的堆，就是使用的该堆。
堆的常用方法：
- 构建优先队列
- 支持堆排序
- 快速找出一个集合中的最小值（或者最大值）
主要支持的操作有：
- 插入一个数
- 查询最小值
- 删除最小值
- 删除一个元素
- 修改一个元素
【从堆的定义到优先队列、堆排序】 10分钟看懂必考的数据结构——堆_哔哩哔哩_bilibili
数据结构：堆（Heap） – 简书 (jianshu.com)
堆和普通树的区别
堆并不能取代二叉搜索树，它们之间有相似之处也有一些不同。我们来看一下两者的主要差别：
节点的顺序。 在二叉搜索树中，左子节点必须比父节点小，右子节点必须必比父节点大。但是在堆中并非如此。在最大堆中两个子节点都必须比父节点小，而在最小堆中，它们都必须比父节点大。
内存占用。 普通树占用的内存空间比它们存储的数据要多。你必须为节点对象以及左/右子节点指针分配内存。堆仅仅使用一个数据来存储数组，且不使用指针。
平衡。 二叉搜索树必须是“平衡”的情况下，其大部分操作的复杂度才能达到O(log n) 。你可以按任意顺序位置插入/删除数据，或者使用 AVL 树或者红黑树，但是在堆中实际上不需要整棵树都是有序的。我们只需要满足堆属性即可，所以在堆中平衡不是问题。因为堆中数据的组织方式可以保证O(log n) 的性能。
搜索。 在二叉树中搜索会很快，但是在堆中搜索会很慢。在堆中搜索不是第一优先级，因为使用堆的目的是将最大（或者最小）的节点放在最前面，从而快速的进行相关插入、删除操作。
堆的维护
原始操作
有两个原始操作用于保证插入或删除节点以后堆仍具有堆序性：
shiftUp(): 如果一个节点比它的父节点大（最大堆）或者小（最小堆），那么需要将它同父节点交换位置。这种操作称为上浮或上滤。shiftDown(): 如果一个节点比它的子节点小（最大堆）或者大（最小堆），那么需要将它向下移动。这种操作称为下沉或下滤。
有时我们也称为我们也称为堆化（heapify），例如在堆排序中建堆
shiftUp 或者 shiftDown 是一个递归的过程，所以它的时间复杂度是 O(logn) 。
其他操作
基于这两个原始操作还有一些其他的操作：
插入
insert(value): 在堆的尾部添加一个新的元素，然后使用shiftUp来修复堆。
删除根
remove(): 移除并返回最大值（最大堆）或者最小值（最小堆）。为了将这个节点删除后的空位填补上，需要将最后一个元素移到根节点的位置，然后使用shiftDown方法来修复堆。
删除任意节点
removeAtIndex(index): 和remove()一样，差别在于可以移除堆中任意节点，而不仅仅是根节点。当它与子节点比较位置不时无序时使用shiftDown()，如果与父节点比较发现无序则使用shiftUp()。当然我们也可以同时调用
shiftDown()和shiftUp()，因为有且只会有一个函数会判断成功并执行。
修改任意节点
changeAtIndex(index): 和removeAtIndex()一样，差别在于可以修改堆中任意节点的值，而不仅仅是根节点。修改后操作同removeAtIndex()，需要进行shiftDown()或shiftUp()操作来修复堆属性。
上面所有的操作的时间复杂度都是 O(log n)，因为 shiftUp 和 shiftDown 都很费时。
还有少数一些操作需要更多的时间：
search(value):堆不是为快速搜索而建立的，但是replace()和removeAtIndex()操作需要找到节点在数组中的index，所以你需要先找到这个index。时间复杂度：O(n) 。buildHeap(array):通过反复调用insert()方法将一个（无序）数组转换成一个堆。如果你足够聪明，你可以在 O(n) 时间内完成。堆排序：由于堆就是一个数组，我们可以使用它独特的属性将数组从低到高排序。时间复杂度：O(nlogn) 。
堆还有一个 peek() 方法，不用删除节点就返回最大值（最大堆）或者最小值（最小堆）。时间复杂度 O(1) 。
注意： 到目前为止，堆的常用操作还是使用
insert()插入一个新的元素，和通过remove()移除最大或者最小值。两者的时间复杂度都是O(log n) 。其其他的操作是用于支持更高级的应用，比如说建立一个优先队列。
建堆
有两种方法，分别对应两种操作
- 自顶向下建堆（上浮方法）
- 自底向上建堆（下沉方法，速度快可以在O(n)时间内完成）
for(int i = n / 2; i>=0; i--) // 由最后一个节点的父节点开始，构建大（小）根堆
heapify(n, i);//下沉方法
shiftDowm()
约定：cnt为数组长度-1，堆数组从1号位置开始使用
void shiftDowm(int i){
int c1 = 2 * i, c2 = 2 * i + 1, mini = i;
if(c1 <= cnt && heap[mini] > heap[c1])
mini = c1;
if(c2 <= cnt && heap[mini] > heap[c2])
mini = c2;
if(mini != i){
swap(mini, i);
shiftDown(mini, i);
}
}
shiftUp()
堆的上滤，可以使用从0开始的数组，和从1开始的数组，不过使用从1开始的数组，代码更简单快捷
//堆数组从1开始
void shiftUp(int i){
while(i / 2 >= 1 && heap[i] < heap[i/2]){
swap(i, i/2);
i /= 2;
}
}
//堆数组从0开始
void shiftUp(int i){
while((i - 1) / 2 >= 0 && heap[i] < heap[(i - 1)/2]){
swap(i, (i - 1)/2);
i = (i - 1) / 2;
}
}
并查集
并查集是一种数据结构，它主要用来处理一些不相交集合的合并问题。常见的用途有求连通子图、求最小生成树、和判断图中是否有环存在。
同时也用于查询图中的两个顶点是不是在同一个集合中。
注意：并查集只回答两个顶点之间是否有一条路径连接，而不回答怎么连接。
具体介绍：
基本操作：
- 初始化init
- 查询find
- 合并merge，分为普通合并和启发式合并(按秩合并)
版本一：不进行路径压缩
int parent[n];
void init(int n)//初始化
{
for(int i = 0; i<n; i++)
parent[i] = i;
}
int find(int x)
{
if(parent[x] == x)//使用-1来标记该节点为孤立节点
return x;//当达到祖先位置时返回
else
return find(parent[x]);//不断向上查找祖先
}
void merge(int x, int y)
{
int x_par = find(x);//找到x的祖先
int y_par = find(y);//找到y的祖先
if(x_par != y_par)//祖先不同时
parent[x_par] = y_par;//将x的祖先指向y的祖先
}
//find的非递归版本
int find(int x) {
while (x != fa[x]) // 如果 x 不是祖先，就一直往上一辈找
x = fa[x];
return x; // 如果 x 是祖先则返回
}
路径压缩，通过上面的代码可以发现，find函数查找的过程中，如果当前节点离祖先越远，那么查找的速度就会越慢，而我们需要的只是当前节点的祖先即可，隐藏可以绕过中间查询过程
int find(int x)
{
if(parent[x] != x)//当前节点不是祖先时，向上寻找
parent[x] = find(parent[x]);//找父亲节点的祖先，并将父亲节点的祖先保存在当前节点上
return parent[x];
}
//容易理解的版本
int find(int x)
{
if(parent[x] == x)
return x;
else
{
parent[x] = find(parent[x]);//递归后最终得到当前孩子的祖先，例如：4->3->1，使用该方法查找，最终得到4的祖先是1
return parent[x];
}
}
路径压缩后得到的结果如下图
启发式合并（按秩合并）
在使用不具备路径压缩时的find时，应当使用启发式合并，这会大大减小树的高度，例如频繁使用merge(1,2)、merge(2, 3)、、、merge(n, n+1)，这种形式的合并，那最后结果得到的树高度为n，这种情况使用find查找时间复杂度又会降低为O（n），因此应当使用启发式合并
//初始化操作
int rank[N];
memset(rank, 0, sizeof(rank));//默认单个节点高度为0
void merge(int x, int y){
int px = find(x), py = find(y);
if(rank[px] > rank[py])
parent[py] = px;
else if(rank[px] < rank[py])
parent[px] = py;
else {
rank[py]++;
parent[px] = py;
}
}
判断图中是否存在环
可以将每一条边看作是一次union，如果在某次union时，检测到两个节点的祖先节点相同，那么在对该两个节点进行union加边，那么势必会造就一个环出来
bool merge(int x, int y){
int px = find(x), py = find(y);
parent[px] = py;
if(px == py)//祖先节点相同，存在环
return true;
else
return false;
}
带权并查集
视频讲解：带权并查集，在视频前三分之一处
查找
//初始化操作
int val[N];
memset(val, 0, sizeof(val));
//val[b]代表b节点到根节点root的权值
int find(int x){
if(x != parent[x]){
int root = find(parent[x]);//先找到根节点
val[x] += val[parent[x]]; //将当前节点与上一个节点到根节点的权值相加
parent[x] = root;//路径压缩，将当前节点直接指向根节点
}
return parent[x];
}
合并
void union(int x, int y, int valx_y){
int px = find(x), py = find(y);
if(px != py){
parent[px] = py;
val[px] = val[y] - val[x] + valx_y; //根据公式：val[px] + val[x] == val[y] + valx_y, valx_y是xy连线的权值
}
}
说白了，就是知道rootx和rooty这两个集合，现在添加了x到y到这条线，希望将两个集合连接起来，但是由于是带权并查集，因此不是简单的讲rootx指向rooty即可，假设以rooty为根，那么要计算rootx指向rooty之后，rootx到根（rooty）的距离是多少。
如上图，现在将rootx指向rooty，val[rootX]到val[rootY]的权值可以由等式 ：val[x] + val[px] == valx_y + val[y]得到，推出val[px] == valx_y + val[y] - val[x]，注意：可以使用向量的思想来进行计算
种类并查集
种类并查集又叫做扩展域并查集。
并查集维护的是若干个元素之间的”关系”，那么种类并查集就是维护若干个元素的多种”关系” 。既然维护的是多种关系，那么就每一种分别维护。那么就出现了若干倍 n 的数组。比如有 4 个人，朋友的朋友是朋友，朋友的敌人是敌人，敌人的朋友是敌人，敌人的敌人是朋友。
在题目中明显给出若干个人之间的关系，比如敌对关系或者是派别关系等，然后要求出可以使其互不干扰会有多少对关系，或者是此时的一个权值等等，都可以用到扩展域并查集。
种类并查集 – OIer某罗 – 博客园 (cnblogs.com)
【笔记】扩展域并查集 – ois 的鸽子窝 – 洛谷博客 (luogu.com.cn)
- 知识搬运
- 种类并查集：即在普通并查集“亲戚的亲戚也是亲戚”的基础上再进行一些“分类”，但是这个分类呢并不是根据物品的种类来进行分类，而是类似“敌人的敌人是朋友”的分类
- 种类并查集常规套路：不是开多个或多维并查集数组，而是扩大并查集规模
举个栗子：我们要维护朋友和敌人这两个关系，则将普通并查集的规模扩大两倍，原来的[1,n]还是存放朋友关系，但是[n+1,2n]则是存放敌人关系，然后每次操作都分别维护
假设：a，b的关系是敌人：b，c的关系是敌人
那么我们将a+n和b（a的敌人是b），b+n和a（b的敌人是a）合并，将b+n和c，c+n和b合并
通过上图可以发现，通过find(a)会找到b+n，find(c)会找到b+n，这样的话通过一个中间量我们建立了a和c的关系。
void merge(int a, int b){
p[find(a)] = find(b + n);
p[find(b)] = find(a + n);
// 并查集的指向并不是一层不变的，对于不同的问题使用不同的指向，有的问题也可能是
// p[find(a + n)] = find(b),p[find(b + n)] = find(a)
}
- [X] 洛谷P1892 团伙 （基础种类并查集）
- [X] 洛谷P2024 食物链 （上文说到的三种循环关系的例题，值得做）扩展域并查集
- 洛谷P1525 关押罪犯 （转换一下题目就是种类并查集，思路比较巧）
- [X] 洛谷P1196 银河英雄传说 （带权并查集）
Trie树
别名字典树、前缀树（prefix tree）、单词查找树，是一种有序树。
典型应用是用于统计，排序和保存大量的字符串（但不仅限于字符串），所以经常被搜索引擎系统用于文本词频统计。
优点：利用字符串的公共前缀来减少查询时间，最大限度地减少无谓的字符串比较，查询效率比哈希树高。
基础数据结构(一) — Trie_哔哩哔哩_bilibili
性质
- 根节点不包含字符，除根节点外的每一个节点都仅包含一个字符
- 从根节点到某一节点路径上所经过的字符连接起来，即为该节点对应的字符串
- 任何节点的所有子节点所包含的字符都不相同
链式存储结构
例题：208. 实现 Trie (前缀树) – 力扣（LeetCode）
1233. 删除子文件夹 – 力扣（Leetcode）【每个节点不在是一个字母，而是一段字符串的处理方法】
class TrieNode {
public:
bool isWord; //根节点到当前节点的路径是一个单词
TrieNode * child[26]; //每个节点有26个分支
TrieNode(){
isWord = false;
for(int i = 0; i<26; i++) child[i] = nullptr;
}
};
class Trie {
TrieNode * root;
public:
Trie() { root = new TrieNode; }
void insert(string word) {
TrieNode * node = root;
for(auto & ch : word){
int u = ch - 'a';
if(node->child[u] == nullptr) node->child[u] = new TrieNode;
node = node->child[u];
}
node->isWord = true;
}
bool search(string word) {
TrieNode * node = root;
for(auto & ch : word){
int u = ch - 'a';
if(node->child[u] == nullptr) return false;
node = node->child[u];
}
return node->isWord;
}
bool startsWith(string prefix) {
TrieNode * node = root;
for(auto & ch : prefix){
int u = ch - 'a';
if(node->child[u] == nullptr) return false;
node = node->child[u];
}
return true;
}
};
/**
* Your Trie object will be instantiated and called as such:
* Trie* obj = new Trie();
* obj->insert(word);
* bool param_2 = obj->search(word);
* bool param_3 = obj->startsWith(prefix);
*/
顺序存储结构
#include <iostream>
using namespace std;
const int N = 1e5 +10;
int son[N][26], cnt[N], idx = 0;
void insert(char str[]){
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!son[p][u]) son[p][u] = ++idx; //0号位置记录根，不存储数据
p = son[p][u];
}
cnt[p] ++;
}
int query(char str[]){
int p = 0;
for(int i = 0; str[i]; i++){
int u = str[i] - 'a';
if(!son[p][u]) return false;
p = son[p][u];
}
return cnt[p];
}
int main(){
int n;
cin >> n;
char op[2], str[N];
for(int i = 0; i<n; i++){
cin >> op >> str;
if(op[0] == 'I')
insert(str);
else
cout << query(str) << '\n';
}
return 0;
}
线段树
看动画，完全搞懂线段树，线段树的算法设计与实现，打ACM必会，动画版+讲师版_哔哩哔哩_bilibili
【数据结构】线段树（Segment Tree）_哔哩哔哩_bilibili
线段树（Segment Tree）是算法竞赛中常用的用来维护 区间信息 的数据结构。线段树是平衡二叉树。
线段树可以在$O(\log N)$的时间复杂度内实现单点修改、区间修改、区间查询（区间求和，求区间最大值，求区间最小值）等操作。
线段树是一种基于分治思想的数据结构。线段树的核心是把一个区间拆分成多个小区间，并用这些小区间的信息来维护整个区间的信息。
线段树通常用一棵二叉树来表示。树的每个节点表示一个区间，节点的左右儿子代表了左右子区间。每个节点存储的值通常是其子区间的信息，比如最小值、最大值、和、乘积等。通过合并左右子区间，就可以得到父节点对应区间的信息。
基本操作：
- 建树（build_tree）
- 区间查询（query）
- 单点修改（modify）
- 更新当前节点（pushup（使用子节点方式更新））
这里以1264. 动态求连续区间和 – AcWing题库，为例子讲解
结构定义
struct node{
int l, r, s; // 区间左右断点，区间和
}SegTree[N * 4]; // 切记要开4n空间
// 更新当前节点
void pushup(int u){
tr[u].s = tr[u * 2].s + tr[u * 2 + 1].s;
}
// 建树
void build(int u, int l, int r){
if(l == r){
tr[u] = {l, r, nums[l]};
return;
}
tr[u] = {l, r, 0};
int mid = l + r >> 1;
build(u * 2, l, mid);
build(u * 2 + 1, mid + 1, r);
pushup(u);
}
// 区间查询
int query(int u, int l, int r){
if(tr[u].l >= l && tr[u].r <= r)
return tr[u].s;
int mid = tr[u].l + tr[u].r >> 1;
int sum = 0;
if(l <= mid)
sum += query(u * 2, l, r);
if(r > mid)
sum += query(u * 2 + 1, l, r);
return sum;
}
// 单点修改
void modify(int u, int p, int v){
if(tr[u].l == tr[u].r){
tr[u].s += v;
return;
}
int mid = tr[u].l + tr[u].r >> 1;
if(p <= mid)
modify(u * 2, p, v);
else
modify(u * 2 + 1, p, v);
pushup(u);
}
关于线段树开4n空间的解释
这里主要介绍的是自顶向下建立线段树版本
自顶向下和自底向上建树的区别：关于线段树的数组到底是开2N还是4N – 知乎 (zhihu.com)
假设叶子有n个元素，考虑如上图的最坏情况（多出一层），由图可以看出倒数第二层有n-1个节点，而倒数第二层之上的节点全部加起来有n-2个（可以通过等比数列前n项和得出），同时可知在考虑空域的情况下，最下一层是上一层的两倍，所以最下一层有2*（n-1）个节点，全部加起来有4n-5，因此为方便起见，我们一般开4n的空间。
基于指针实现的线段树
接下来我们来搭建一棵线段树：
首先，定义一个结构体节点，包含左右儿子指针和维护的信息。
struct node {
int l, r;
int sum;
node *left, *right;
};
然后，定义一个建树函数，用递归的方式建立线段树。
node* build(int l, int r) {
node* root = new node(l, r);
if (l == r) {
return root;
}
int mid = (l + r) >> 1;
root->left = build(l, mid);
root->right = build(mid + 1, r);
return root;
}
接下来，我们来实现区间查询操作。对于区间查询，我们可以采用递归遍历线段树的方式，在每个节点中查询对应的区间信息。假设我们需要查询区间 [query_l, query_r] 的信息，我们可以从根节点开始判断当前节点表示的区间和查询区间是否有交集，如果有交集，则递归查询其左右子区间的信息，并合并得到查询结果。
int query(node* root, int query_l, int query_r) {
if (!root || root->l > query_r || root->r < query_l) {
return 0; // 当前节点区间和查询区间无交集
}
if (root->l >= query_l && root->r <= query_r) {
return root->sum; // 当前节点区间被包含在查询区间中
}
// 否则递归查询左右子区间
int mid = (root->l + root->r) >> 1;
return query(root->left, query_l, query_r) + query(root->right, query_l, query_r);
}
最后，我们来实现区间更新操作。对于区间更新，我们也可以采用递归遍历线段树的方式，在每个节点中更新对应的区间信息。假设我们需要把区间 [update_l, update_r] 中的每个节点的值加上一个常量 k，我们可以从根节点开始判断当前节点表示的区间和更新区间是否有交集，如果有交集，则递归更新其左右子区间的信息。
void update(node* root, int update_l, int update_r, int k) {
if (root->l > update_r || root->r < update_l) {
return; // 当前节点区间和更新区间无交集
}
if (root->l >= update_l && root->r <= update_r) {
root->sum += k; // 更新当前节点区间
return;
}
// 否则递归更新左右子区间
update(root->left, update_l, update_r, k);
update(root->right, update_l, update_r, k);
root->sum = root->left->sum + root->right->sum; // 合并左右子区间的信息
}
以上就是基本的线段树实现方式，通过建树、查询和更新操作，我们可以使用线段树来解决各种区间查询问题。当然，在实际应用中，线段树还有很多变种和优化，比如懒标记、扫描线算法等，可以根据具体的应用场景来选择不同的实现方式。
哈希表
哈希（hash table）表又称散列表，一种以「key-value」形式存储数据的数据结构。所谓以「key-value」形式存储数据，是指任意的键值 key 都唯一对应到内存中的某个位置。只需要输入查找的键值，就可以快速地找到其对应的 value。可以把哈希表理解为一种高级的数组，这种数组的下标可以是很大的整数，浮点数，字符串甚至结构体。
哈希表是一种不同于线性表的数据结构，哈希表的查询速度非常快，时间复杂度通常为
O(1)（在理想状态下，不考虑哈希冲突，时间复杂度就是O(1)）。
介绍哈希表我们需要先介绍哈希函数，哈希函数满足如下两个特点
- 相同的输入映射到相同的索引
- 不同的输入映射到不同的索引
基本操作
add(KEY key, VALUE value)将一对新的键值对添加到哈希表get(KEY key)通过特定的关键字拿到其对应的数值remove(KEY key)通过关键字，删除哈希表中的键值对getSize()查看键值对的数量isEmpty()查看哈希表是否为空
哈希冲突
当然，这是在理想情况下，不考虑空间和时间上的因素，哈希函数可以将不同的输入映射到不同的索引。但现实情况是，我们需要考虑时间和空间上的开销，因此我们并不是百分百能将不同的输入映射到不同的值上。因此我们需要考虑，如果出现不同的输入映射到相同的索引上时，如何解决，这个问题也称之为哈希冲突。
存储方式
链表法
链表法也称为拉链法，是在每个存放数据的地方开一个链表，如果有多个键值索引到同一个地方，只用把他们都放到那个位置的链表里就行了。查询的时候需要把对应位置的链表整个扫一遍，对其中的每个数据比较其键值与查询的键值是否一致。
拉链法类似于链式前向星、顺序邻接表，使用数组模拟指针。
const int N = 1e5+3; // 取大于1e5的第一个质数，取质数时，哈希冲突的概率最小，原因请google
int h[N], e[N], ne[N], idx = 0;
memset(h, -1, sizeof(h));
void insert(int x){
int k = (x % N + N) % N;
// 假定x的范围在[-1e9, 1e9], 需要映射到1e5的空间上去，那么映射的结果不能为负数，必需为正数，使用这种方式可以避免映射结果都为正数
e[idx] = x, ne[idx] = h[k], h[k] = idx++;
}
bool query(int x){
int k = (x % N + N) % N;
for(int i = h[k]; i != -1; i = ne[i])
if(e[i] == x)
return true;
return false;
}
线性探测法
线性探测法又名开放寻址法，把所有记录直接存储在哈希表中，如果发生冲突则根据某种方式继续进行探查。
比如线性探查法：如果在
k处发生冲突，就依次检查k + 1，k + 2……直到找到一个未使用的位置，将该值存入。
const int N = (1e5+3) * 2; //使用开放寻址法需要的空间一般设置为数据范围的两倍到三倍
const int INF = 0x3f3f3f3f;
int h[N];
memset(h, 0x3f, sizeof(h));
int find(int x){
int k = (x % N + N) % N;
while(h[k] != INF && h[k] != x){
k++;
if(k == N) k = 0; // 如果到最后一个位置都是被使用的，那就从头检查是否有可以存储的位置
}
return k;
}
字符串哈希
全称
字符串前缀哈希法，把字符串变成一个p进制数字（哈希值），实现不同的字符串映射到不同的数字。
对形如$X_1X_2X_3⋯X_{n−1}X_{n}$的字符串,采用字符的 ascii 码乘上 P 的次方来计算哈希值。映射公式: $(X_1 \times P^{n-1} + X_2 \times P^{n-2} + \cdots + X_{n-1} \times P^1 + X_n \times P^0) \bmod Q$
注意点：
- 任意字符不可以映射成0，否则会出现不同的字符串都映射成0的情况，比如A,AA,AAA皆为0
- 冲突问题：通过巧妙设置P (131 或 13331) , Q ($2^{64}$)的值，一般可以认为为不产生冲突
- 由于哈希值一般较大，所以推荐使用
unsigned long long，同时由于需要mod（$2^{64}$$），而unsigned long long恰好是$$2^{64}$$，当值超过unsigned long long时，也就相当于mod了$$2^{64}$
- 前缀和公式：$h[i] = h[i-1] \times P + str[i]$
- 区间和公式：$h[l,r]=h[r]-h[l-1] \times p[r – l + 1]$
举例：例如对于ABCDE和ABC的前三个字符是一样的，只差两位，如果直接用ABCDE的哈希值减去ABC的哈希值，得到的结果并不是DE的哈希值，只有把ABC变为ABC00，然后在使用ABCDE - ABC00才能得到DE的哈希值，即如上公式所示，需要乘以p[r - l + 1]，将ABC变为ABC00
扩展例题：139. 回文子串的最大长度 – AcWing题库
总结
无论使用那种方法，在理想情况下，时间复杂度都是O(1)的。如果存在大量哈希冲突，那么最坏时间复杂度将达到O(n)。哈希冲突的解决办法就是选择一个良好的哈希函数，使得任意不同的输入能映射到不同的索引上。
