0x14哈希之兔子兔子

佚名 7年前 (2019-04-12) 随笔 1305人围观抢沙发百度已收录

参考链接：https://www.cnblogs.com/wyboooo/p/9813428.html

题目链接：https://www.acwing.com/problem/content/140/

SRE实战互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。

将哈希算法用于字符串匹配的原理非常简单。对于每个起始位置，我们不是O（m）地直接比较字符串是否匹配，而是O（l）地比较长度为m的字符串子串地哈希值与T地哈希值是否相等。虽然即使哈希值相等也未必相等，但如果哈希值是随机分布地话，不同的字符串哈希值相等的概率是很低的，可以当作这种情况不会发生。
但是，如果我们采用O（m）的算法计算长度为 m地字符串子串地哈希值的话，那复杂度还是O（nm）。这里我们要使用一个叫做滚动哈希的优化技巧。选取两个合适的互素常数b和h(l<b<h)，假没字符串C=c1c2c3...cm,定义哈希函数

H(C) = (c₁b^m-1 + c₂b^m-2 + c₃b^m-3 + ... + c_mb⁰) mod h

其中b是基数，相当于把字符串看做b进制。这项在计算S中m长的字串时，每向后滑动一个字符之后的字串的hash值和上一次字串的hash值有如下关系：

H(S[k+1.. k+m]) = H(S[k..k+m-1] * b - s_kb^m + s_k+m)mod h

这样计算hash值就可以在O(n)的时间内算出S中所有位置对应的hash值，从而在O(m + n)的时间内完成字符串匹配。

Hit:实际使用时取h为2⁶⁴，使用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)*P^length(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;
	}
}