字符串哈希
简单说就是把一个字符串映射成一个数字
具体点，就是把一个字符串如”ABC”映射成一个p进制的数字
“ABC” –> p^2+A + p^1+B + p^0+C = 哈希值， 一般p取131或13331
本题需要求到一个字符串中任意两个区间的子串是否相同
可以转换为求两个区间子串的哈希值是否相等
思路：
用前缀和的思想，求出前缀字符串的哈希值
举例说明：
"ABCDEFGHI"
123456789 (下标)
L R
字符串"A"的 哈希值为 p^0+A
字符串"AB" 哈希值为 p^1+A + p^0+B
字符串"ABC" 哈希值为 p^2+A + p^1+B + C
字符串[1,L-1]的哈希值为 p^3+A + p^2+B + p^1+C + p^0+D
字符串[1,R] 的哈希值为 p^8+A + p^7+B + ... + P^0+I
那么如何求[L,R]字符串的哈希值呢，根据前缀和的思想，就是h[R] - h[L-1] (h[R]表示从[1,R]的字符串哈希值)
但是发现h[R]从[1,L-1]这一段left，每个数都比right这一段多乘了p^(R-(L-1))
所以字符串从[L,R]的哈希值为h[R] - h[L - 1] * p^(R-(L-1)) = h[R] - h[L - 1] * p^(R-L+1)
import java.io.*;
class Main{
static BufferedReader read = new BufferedReader(new InputStreamReader(System.in));
static BufferedWriter log = new BufferedWriter(new OutputStreamWriter(System.out));
public static void main(String[] args) throws Exception{
String[] s = read.readLine().split(" ");
int n = Integer.valueOf(s[0]);
int t = Integer.valueOf(s[1]);
String w = read.readLine();
int P = 131;
long[] h = new long[n + 10];
long[] p = new long[n + 10];
p[0] = 1;
for(int i = 1; i <= n; i++){
p[i] = p[i - 1] * P;
h[i] = h[i - 1] * P + w.charAt(i - 1);
}
while(t-- > 0){
s = read.readLine().split(" ");
int l1 = Integer.valueOf(s[0]); int r1 = Integer.valueOf(s[1]);
int l2 = Integer.valueOf(s[2]); int r2 = Integer.valueOf(s[3]);
String out = h[r1] - h[l1 - 1] * p[r1 - l1 + 1] == h[r2] - h[l2 - 1] * p[r2 - l2 + 1] ?
"Yes" : "No";
log.write(out + "\n");
}
log.flush();
}
}
兄弟你来搞笑的把p^0+A 你确定是加法？ 不是乘法 我服了 建议下次写题解反复自己看读三遍
你才是来搞笑的，还笑题解，自己去网上看看哈希模型
y总讲课的时候讲的是乘法，写代码的时候实际是加法，身体很诚实哈哈
试了下，用乘法，long long 也会越界
h[1] = h[0]×p+str[0] = 0×p + A=A
h[2] = h[1]×p+str[1] = A×p + B
h[3] = h[2]×p+str[2] = A×p^2 + B×p + C
进制计算来的吧，讲的和写的没有任何冲突
本来就是加法，你自己搞错了吧
哇擦，大佬牛逼！~
new B !
y总说是对2的64次方取模，但是java中long最大才2的31次方减一，请问这样能保证正确性吗？
java的int是4字节32位， long是8字节64位， 2的64次方减一
笔误笔误，谢谢提醒
不过long是2的63次方减一
有道理！
因为，2^64 = 2^63 + (2^63-1) + 1
Java中数据为有符号整数，Int的最大值只有2的31次方-1，Long最大只有2的63次方-1
java没有无符号的变量类型，难道不要做取模运算吗？
没明白什么意思， 如果是越界问题的话，我一开始就定义成long了， 所以不会越界哈
Y总教的时候用C++写的，所以有无符号类型，溢出直接就取模了。但是Java没有无符号类型，溢出可能出现负数导致结果错误。所以就想问问。
是的，你说的没错， java溢出就是负数了
我应该知道为什么对了，java使用的都是补码，所以加减都是补码相加。所以所有溢出的结果都是截断的正确的正整数结果，相当于取模了。
大佬，我还是不太明白你什么意思，说得能再详细点吗？（最好举几个栗子）
java试一试Integer.MAX_VALUE+1，你用二进制计算一下正确的情况，然后对比一下打印结果，是不是把符号位当作普通的一位算进去就是正确结果。还不行就Integer.MAX_VALUE+2。。。试一试。
可是(Integer.MIN_VALUE)是一个负数啊．如果将其模上(Integer.MAX_VALUE)得到的还是负数呀？怎么就映射到从0~Integer.MAX_VALUE-1去了呢？
操作中没有取模，这里取模是利用java自动截断实现的。超过2^32大小的数自动取模（即截断操作）。而且不是映射到0-Integer.MAX_VALUE上，而是映射到0-2^32上面，只是打印的时候会把第一位当作符号位，我们私底下其实可以认为其就是32位无符号整数。
加减乘补码操作与数字正负完全没有关系，但是涉及除法就不行了。取模（也涉及到了除法）和除法参与的话是不能再私下看作无符号整数类型了。
哦，我想明白了．但是我在考虑这个映射方法跟直接对2的32次方取模所得到的映射结果不一致，这样也行嘛？
你考虑一下除法是如何计算的，这里是需要考虑符号的情况的。比如4位的计算1000，如果我们当作无符号整数计算的话除以2应该是0100，但是按照有符号的补码计算的结果并不如此，因为补码除法在运算前需要检测符号位，进行预处理。
取模就更复杂了。
带余数除法：a = kb+r (0<=r<|b|)，计算过程：先求k然后根据a-kb求出r为数学上的取模运算，其中k为b/a下取整。但是java的k取值不是下取整，而是向0靠近取k值，所以涉及到负数的取模运算就会得到和数学上取模运算不太一样的结果（虽然取余等式是一致的）。-7%2在java运算中是，k=-3，r=-1；数学（python是向下取整，可以用python试一试）上，k=-4，r=1。
因此但凡涉及到这两个操作的话，我们是不能再使用这个小技巧了。
牛逼！
好解释