Hash大法

内容参考《算法竞赛进阶指南》

之前集训的时候听老师讲过，字符串题目中，hash一般不是正解，但是是一个优秀的暴力，可以拿比较多的部分分。

hash涉及内容很多，这里只讨论字符串hash

可以把字符串看成一个131进制位数，然后用ull储存，大过2的64次方后自动取模。

这样的话hash值相等的话可以认为两个字符串是一样的（极少概率不一样）

所以对于一个字符串，我们可以用O（n）的时间内算出所有前缀的hash值，然后就可以用

O（1）的时间算出任意一段区间的hash值（类比二进制操作，具体看代码）。

Hash大法吼啊！！！

怎么用呢？

问题：给你一个字符串，每次询问两个区间[l1, r1][l2, r2],判断两个区间的字符是否相等

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef unsigned long long ull;

const int MAXN = 1e6 + 10;

const int base = 131;

char s[MAXN];

int n, q;

ull p[MAXN], f[MAXN];

inline ull cut(int l, int r)

{

	return f[r] - f[l - 1] * p[r - l + 1];

}

int main()

{

	scanf("%d%d", &n, &q); //n为字符串长度

	scanf("%s", s + 1);

	p[0] = 1;

	_for(i, 1, n)

	{

		f[i] = f[i - 1] * base + (s[i] - 'a' + 1);

		p[i] = p[i - 1] * base;

	}

	while(q--)

	{

		int l1, r1, l2, r2;

		scanf("%d%d%d%d", &l1, &r1, &l2, &r2);

		if(cut(l1, r1) == cut(l2, r2)) puts("Yes");

		else puts("No");

	}

	return 0;

}

用Hash大法解决kmp问题

比较hash值就好了，非常简单粗暴！！！（但效率比KMP慢一些，所以说是一个优秀的暴力）

caioj 1177 KMP模版

#include<bits/stdc++.h>

#define REP(i, a, b) for(register int i = (a); i < (b); i++)

#define _for(i, a, b) for(register int i = (a); i <= (b); i++)

using namespace std;

typedef unsigned long long ull;

const int MAXN = 1e6 + 10;

const int base = 131;

char a[MAXN], b[MAXN];

int n, q, lena, lenb;

ull p[MAXN], f[MAXN], t;

inline ull cut(int l, int r)

{

	return f[r] - f[l - 1] * p[r - l + 1];

}

int main()

{

	scanf("%s%s", a + 1, b + 1);

	lena = strlen(a + 1); lenb = strlen(b + 1);

	p[0] = 1;

	_for(i, 1, lena)

	{

		f[i] = f[i - 1] * base + (a[i] - 'a' + 1);

		p[i] = p[i - 1] * base;

	}

	_for(i, 1, lenb) t = t * base + (b[i] - 'a' + 1);

	_for(i, 1, lena)

	{

		if(cut(i, i + lenb - 1) == t)

		{

			printf("%d %d\n", i, i + lenb - 1);

			break;

		}

		if(i == lena) puts("NO");

	}

	return 0;

}

巴特西

Hash大法

最新文章

热门文章