博客

浅谈字符串哈希（持续更新）

我们先来看一个经典的求某个前缀的字符串的哈希值的代码片段

typedef unsigned long long ULL;
P = 131;
ULL h[1000],p[1000];//数组h代表一个前缀的哈希值
void make_hash()
{
	char str[1000];
	memset(str,'\0',sizeof str);
	scanf("%s",str + 1);//字符串应从下标1开始输入
	int p[0] = 1;
	for(int i = 1; i  <= str.length; i++)
	{
		p[i] = p[i-1] * P;
		h[i] = h[i-1] * P + str[i];
	}
}

ULL get(int l,int r)//用于求某个区间内的哈希值
{
	return h[r] - h[l-1] * p[r-l+1];
}

数组p[]其实没什么大问题，就是用于存储131的次方的值，如131^0 = 1,131^131 = …

下面咱来说一下这个h[i] = h[i-1] * P + str[i];到底是个啥：

以字符串’ABCD’为例

h[0]存储的是前零个(空串)对应的哈希值即为0

h[1]存储的是前一个字符对应的哈希值即’A’对应的哈希值

h[2]存储的是前两个字符对应的哈希值即’AB’对应的哈希值

h[3]存储的是前三个字符对应的哈希值即’ABC’对应的哈希值

试想，是否存在一种递推关系:用h[i-1]求出h[i]?

答案是肯定的，这个递推关系就是

h[i] = h[i -1] * P + str[i];

先来模拟两组数据，以’A’,’AB’为例

已知A对应的哈希值h[i]

如果说’A’中A是“个位”的话

那么’AB’中A就应该是“十位”，B就是个位

那么如果想通过’A’来计算’AB’第一步就应该将’A’中的A前移一位，而移动的方法就是

h[i] * P(P实际上是进制，即131进制)

这种方法如果换位数字应该就很好理解了:

如现在已经知道了一个数字 1

可以用1来计算12

方法同上

先将1先左移动一位:1*10(10是十进制)

12 = 1 * 10 + 2(2是12的个位)

上面这个式子是不是很眼熟?

实际上与

h[i] = h[i - 1] * P + str[i] 

的原理是一样的。

（博主这几天有一些任务，实际上是学一些还未学过的算法，等任务完成后继续回来更新其余代码片段）

有问题您就来问我，别偷偷藏在心里。