核心思想与应用

1. 应用

利用字符串前缀哈希方法快速判断同一个字符串两个不同区间是否相等；如果hash值相等等价于两个区间相同；否则两个区间不等

2. 处理步骤

step1: 把字符串看成P进制数
step2：预处理字符串所有的前缀hash值, hash[i] = (hash[i - 1] * P + str[i]) mod Q, 这里P一般取131或者13331，Q取2^64
step3: 计算区间hash值hash[l, r] = hash[r] - hash[l-1] * p[r - l + 1]

代码注意点

1. 由于 Q取2^64次方，可以直接用 unsigned long long存取 h[N]、p[N]
2. 计算区间时候需要用到 P的 n次方，需要预处理，特别注意 p[0] = 1

代码模板

const int N = 100010;
const int P = 131;
ULL h[N], p[N];

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

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