字符串前缀散列是将字符串前缀映射成unsigned long long整数，有两个步骤：
(1)将字符串前缀看成p进制数（字符看成其ASCII码），换算成十进制数（利用字符串前缀数组可以计算任意子串对应十进制数，进而用十进制数是否相等来判断子串是否相同）；
(2)将字符串前缀对应的十进制数对q取模，计算散列值（由于字符串前缀计算出来的十进制数数值过大，但是个数较少，因此将其散列到[0, q-1]范围内）。
两个小技巧：
(1)p取经验值131或13331，则发生冲突概率很小，通常不需要处理冲突；
(2)q取$2^{64}$，则将整数用unsigned long long存储时，溢出的过程就是取模的过程。
hash[n+1]不是散列表，而是用hash[i]存储字符串前缀str[1...i]的散列值；place[i]存储$p^i$ % $2^{64}$，使得在计算子串散列值时不需要每次使用循环计算place[i]；
unsigned long long hash[n+1], place[n+1];
字符串前缀散列值数组hash[n+1]必须在前部有0边界，即hash[0] = 0；为了对应，字符串从str+1开始存储；place[0]初始化为1（$p^0$ = 1）；
scanf("%s", str+1);
hash[0] = 0, place[0] = 1;
for (int i = 1; i <= n; i++) {
hash[i] = hash[i-1] * p + str[i];
place[i] = place[i-1] * p;
}
计算子串str[l...r]的散列值：
hash[l...r] = hash[r] - hash[l-1] * place[r-l+1];