字符串哈希
将字符串的信息压缩到一个信息里面,一般压成一个值。
多项式哈希:
形如 \(h(s)=\sum\limits^{\left|s\right|}_{i=1}s_ibase^{i-1}\) 的哈希。
例:"abbab"
,使 a
为 \(1\),b
为 \(2\),base
为 \(7\),
注:直接用 s[i]-'a'
会使得 a
的值为 \(0\),导致 a
,aa
,aaa
值相同。
所以用 s[i]-'a'+1
会好一点。
base 比较小容易调试,可以设 \(29\)。
(《可以给人看的》人言否!)
多项式哈希会出一点问题,例:"ab"
+"cd"
="ad"
+"cb"
。
矩阵哈希:
将字符串映射为一个数组,将字符串中各个字符代表的矩阵乘起来即为值。