参考链接：https://www.cnblogs.com/wyboooo/p/9813428.html
题目链接：https://www.acwing.com/problem/content/140/
将哈希算法用于字符串匹配的原理非常简单。对于每个起始位置，我们不是O（m）地直接比较字符串是否匹配，而是O（l）地比较长度为m的字符串子串地哈希值与T地哈希值是否相等。虽然即使哈希值相等也未必相等，但如果哈希值是随机分布地话，不同的字符串哈希值相等的概率是很低的，可以当作这种情况不会发生。
但是，如果我们采用O（m）的算法计算长度为 m地字符串子串地哈希值的话，那复杂度还是O（nm）。这里我们要使用一个叫做滚动哈希的优化技巧。选取两个合适的互素常数b和h(l<b<h)，假没字符串C=c1c2c3...cm,定义哈希函数
H(C) = (c1bm-1 + c2bm-2 + c3bm-3 + ... + cmb0) mod h
其中b是基数， 相当于把字符串看做b进制。这项在计算S中m长的字串时，每向后滑动一个字符之后的字串的hash值和上一次字串的hash值有如下关系：
H(S[k+1.. k+m]) = H(S[k..k+m-1] * b - skbm + sk+m)mod h
这样计算hash值就可以在O(n)的时间内算出S中所有位置对应的hash值，从而在O(m + n)的时间内完成字符串匹配。
Hit:实际使用时取h为264，使用long long int 自然溢出省去取模时间。
PS:原始的R-K算法还需要检查哈希值冲突，但这样会使算法复杂度退化为O(mn)，比赛时只比较不检查。
字符串Hash函数把一个任意长度的字符串映射成一个非负整数，并且其冲突概率几乎为零。
去以固定值P,把字符串看成P进制数，并分配一个大于0的数值，代表每种字符。取一个固定值M,求出该P进制数对M的余数，作为该字符串的Hash值。
一般来说取P=131或P=13331。通常取M = 2^64，也就是直接使用unsigned long long存储这个Hash值，产生溢出时相当于自动对2^64取模。
只要Hash值相同，我们就可以认为原字符串是相等的。
上述Hash算法很难产生冲突，一般情况下完全可以用在题目的标准解答中。还可以多取一些恰当的P和M的值，多进行几组Hash运算。
如果已知字符串S的Hash值为H(S)，那么在S后添加一个字符c的新字符串的Hash值就是H(S+c)=(H(S)*P+val[c])modM
如果已知字符串S的Hash值为H(S)，字符串S+T的Hash值为H(S+T)，那么字符串T的Hash值H(T)=(H(S+T) -H(S)*Plength(T))mod M
c++代码：
#include <iostream>
#include <set>
#include <cmath>
#include <stdio.h>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
#define inf 0x7f7f7f7f
const int maxn = 1e6 + 5;
char s[maxn];
int m;
int l1, r1, l2, r2;
unsigned long long H[maxn], p[maxn];
int main()
{
scanf("%s", s+1);
int n = strlen(s + 1);
p[0] = 1;
H[0] = 0;
for(int i = 1; i <= n; i++){
H[i] = H[i - 1] * 131 + (s[i] - ‘a‘ + 1);
p[i] = p[i - 1] * 131;
}
scanf("%d", &m);
while(m--){
scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
if(H[r1] - H[l1 - 1] * p[r1 - l1 + 1] == H[r2] - H[l2 - 1] * p[r2 - l2 + 1]){
puts("Yes");
}
else{
puts("No");
}
}
}
Java代码：
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStream;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.io.PrintWriter;
import java.util.StringTokenizer;
public class Main {
public static InputReader in = new InputReader(System.in);
public static PrintWriter out = new PrintWriter(new OutputStreamWriter(System.out));
static int maxn=10000005;
static int[]H=new int[maxn];
static int[]p=new int[maxn];
public static void main(String[] args) throws Exception {
while(in.hasNext()) {
String s=in.next();
int n=s.length();
s=" ".concat(s);
p[0]=1;
H[0]=0;
for(int i = 1; i <= n; i++){
H[i] = H[i - 1] * 131 + (s.charAt(i) - ‘a‘ + 1);
p[i] = p[i - 1] * 131;
}
int m=in.nextInt();
while(m!=0) {
m--;
int l1=in.nextInt();
int r1=in.nextInt();
int l2=in.nextInt();
int r2=in.nextInt();
if(H[r1] - H[l1 - 1] * p[r1 - l1 + 1] == H[r2] - H[l2 - 1] * p[r2 - l2 + 1]){
out.println("Yes");
}
else{
out.println("No");
}
}
out.flush();//写在最后
}
out.close();
}
}
class InputReader{
private final static int BUF_SZ = 65536;
BufferedReader in;
StringTokenizer st;
public InputReader(InputStream in) {
super();
this.in = new BufferedReader(new InputStreamReader(in),BUF_SZ);
st = new StringTokenizer("");
}
public boolean hasNext() throws IOException {
while(!st.hasMoreTokens()){
String line = nextLine();
if(line == null){
return false;
}
st = new StringTokenizer(line);
}
return true;
}
public String next() throws IOException{
while (!st.hasMoreTokens()) {
try {
st = new StringTokenizer(in.readLine());
} catch (IOException e) {
throw new RuntimeException(e);
}
}
return st.nextToken();
}
public int nextInt() throws IOException {
return Integer.parseInt(next());
}
public double nextDouble() throws IOException {
return Double.parseDouble(next());
}
public double nextLong() throws IOException {
return Long.parseLong(next());
}
public String nextLine() throws IOException {
String line = "";
line = in.readLine();
return line;
}
}
原文：https://www.cnblogs.com/clarencezzh/p/10694058.html