字符串哈希_牛客博客

字符串哈希就是将一个字符串映射成一个P进制的数，然后用前缀记录下来，当你查询某个字符串的哈希值时，只要用前缀相减就可以了。通常P取131或者13331来尽可能减少冲突，同时用unsigned long long值过大自动溢出避免手动取模

eg：s[] = "ABACBDAB"， h是前缀和，v是字符的值

h[1] = v[A]， h[2] = h[1] * P + v[B]，h[3] = h[2] * P + v[A] ... h[7] = h[6] * P + v[A]，h[8] = h[7] * P + v[B]

当求某个子串的哈希值时，由于我们这里看到的是

"ABACBDAB" = A * P^7 + B * P^6 + A * P^5 + C * P^4 + B * P^3 + D * P^2 + A * P^1 + B * P^0

那么如果求子串"CBD"的哈希值，则就是说"CBD" = C * P^2 + B * P^1 + D * P^0 (1)

而在母串中"CBD" = C * P^6 + B * P^5 + D * P^4 (2)

根据前缀和的思想，"CBD" = h[6] - h[3]得到的结果是(2)，而我们要得到的结果是(1)

故我们需要对其进行处理：
对于P进制的数的表示：

h[6]是 ABACBD

h[3]是 ABA

故如果要得到4~6的哈希值则：有hash[4~6] = h[6] - h[3] * P^(6 - 4 + 1)

判断两个子串就是分别求出两个子串哈希值判断下即可。