[AcWing]841. 字符串哈希（C++实现）字符串哈希模板题）

• 1. 题目
• 2. 读题（需要重点注意的东西）
• 3. 解法
• 4. 可能有帮助的前置习题
• 5. 所用到的数据结构与算法思想
• 6. 总结

思路：要快速判断两个字符串是否相等的时候，可以用字符串哈希；相应的题目可以直接搜哈希的题目
核心思想：用p进制的角度，将字符串看成是一个数字

然后可以用该前缀哈希值得到所有子串的哈希值

比较难以理解的地方在于P的含义与公式的理解以及代码中的预处理p和h数组，其解释详见 3.解法 中的可能出现的问题

---------------------------------------------------解法---------------------------------------------------

#include 
#include 

using namespace std;



// 用ULL来模2的64次方，需要模2的64次方时都可以直接用ULL来做
// 模2的64次方是为了把任何一个字符串映射到从0带2的64次方-1之间的一个数
typedef unsigned long long ULL;

// P进制，P为经验值：取131或者13331
const int N = 100010, P = 131;

int n, m;
char str[N];
ULL h[N], p[N];

//---------------------核心代码开始-----------------------
// 得到l到r直接的哈希值，l为高位，r为低位
ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1];
}
//---------------------核心代码结束-----------------------

int main()
{
    scanf("%d%d", &n, &m);
    
    // str+1表示从下标为1开始存储
    scanf("%s", str + 1);

    p[0] = 1; // p的0次方等于1
    
    // 预处理p数组和哈希数组h
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + str[i]; // 将字符转换成P进制的数，+ 的 str[i] 是字符的ASCII码值
        p[i] = p[i - 1] * P;
    }
    
    // m次询问
    while (m -- )
    {
        int l1, r1, l2, r2;
        scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
        
        // 如果两个区间的哈希值相同，则字符串相同；否则不同
        if (get(l1, r1) == get(l2, r2)) puts("Yes");
        else puts("No");
    }

    return 0;
}

可能存在的问题

1. p和h数组的理解

    p数组用来存储h要乘的p的多少次方
    
    h数组用来存储每个前缀字符串的哈希值
        如str = "ABCD"
        h[0] = 0;
        h[1] = "A"的哈希值（将字符转换成p进制的一个数字）
        h[2] = "AB"的哈希值（将字符转换成p进制的一个数字）
        h[3] = "ABC"的哈希值（将字符转换成p进制的一个数字）
        h[4] = "ABCD"的哈希值（将字符转换成p进制的一个数字）

2. 公式的理解

		把前l-1位乘上p的r-l+1次方（相当于对齐位数并补0），再用h[r]减去这个数即可

        举个例子：

		有一个字符串ABCDE ，下标从0开始
        
        输入l = 1, r = 3
        
        假设哈希值计算出来如下：
        
        h[3] = 1234
        h[1] = 12
        h[0] = 1
        
        则根据公式：h[r] - h[l - 1] * p[r - l + 1]
        
        得到：
        h[3] - h[1 - 1] * p[3 - 1 + 1] = 1234 - 1*1000 = 234
        
        即这个234就表示了[l,r]的哈希值（注意是左闭右闭）
        
        p[i]数组表示p的i次方的值是多少

3. 预处理的代码

    // 预处理p数组和哈希数组h
    for (int i = 1; i <= n; i ++ )
    {
    	// 预处理字符串前缀和
        h[i] = h[i - 1] * P + str[i]; // 将字符转换成P进制的数，+ 的 str[i] 是字符的ASCII码值
        // 预处理数组p[]，p[i]数组表示的是p的i次方的值是多少
        p[i] = p[i - 1] * P; // 即 p[1] = P ,p[2] = P*P,p[3] = P^3
    }

字符串哈希用数组实现的模板题，推荐完全背下来。