字符串哈希

                     

贡献者: 有机物

   字符串哈希和普通的哈希算法类似,字符串哈希是把一个很长的字符串变成一个整数,这样的好处是:如果想比较两个很长的字符串是否相等时,普通算法是遍历一遍整个字符串,如果其中一个字符串的字符和另一个字符串的字符不等,则两个字符串不一样。时间复杂度为 $O(N)$。而用字符串哈希的话可以直接比较两个字符串的哈希值是否相同,时间复杂度为 $O(1)$。下面介绍一种哈希方式可以把任意一个字符串变成一个非负整数,并且哈希冲突的概率几乎为 $0$。

   哈希函数通常设计为:取一固定值 $P$,把字符串看作 $P$ 进制数,并分配一个大于 $0$ 的数值,代表每种字符。再取一固定值 $M$,求出 $P$ 进制数转换十进制的数对 $M$ 的余数,作为这个字符串的哈希值。一般来说,$p$ 取 $131$ 或 $13331$ 时出现冲突的概率几乎为 $0$,通常 $M$ 取 $2^{64}$,可以直接用 unsigned long long 这个变量类型存储哈希值,溢出时就相当于对 $2^{64}$ 取模。

   举个例子: 先把一个字符串 $\text{abcfea}$ 变成 $p$ 进制数,将字符 $a \sim z$ 映射成 $1 \sim 26$,所以原来的字符串就变成了:$(123651)_p$,转化为十进制就为:

\begin{equation} 1 \times p^5 + 2 \times p^4 + 3 \times p^3 + 6 \times p^2 + 5 \times p^1 + 1 \times p^0~, \end{equation}
相加得出答案:$39175337388$ 作为这个字符串的哈希值。

   一般在做哈希的时候,存储哈希的数组会存字符串的前缀哈希值,比如用 h 数组存储字符串的哈希值,h[1] = a 的哈希值,h[2] = ab 的哈希值,这样以此类推。那怎么算前缀哈希值呢?比如我们已经知道了 hash(S) 的哈希值,那么在字符串 $S$ 后面添加一个字符串 $C$ 构成的新字符串的哈希值为:hash(S+C) = hash(S) * P + value[C]。乘 $P$ 就相当在 $P$ 进制下于左移一位,加 value[C] 就是字符串 $C$ 所分配的数值。

   举个例子:比如我们知道 hash(abc),想算 hash(abcd) 的话就是:hash(abc) * P + value[d]

   S = "abc"C = "d"

   $S$ 表示为 $P$ 进制数:$(123)_p$,$C$ 表示为 $P$ 进制数:$(4)_p$

   hash(S) = $1 \times p^2 + 2 \times p^1 + 3 \times p^0=17426 $

   hash(S+C) = $1 \times p^2 *p + 2 \times p^1*p + 3 \times p^0*p + 4 = 1 \times p^3 + 2 \times p ^ 2 + 3 \times p^1 + 4=2282810 $

   hash(abc)=17426hash(abc) * 131+4 = 17426 * 4 + 4 = 2282810

   这样就有了第一个公式:

   hash(S+C) = hash(S) * P + value[C]

   我们还可以通过前面算的所以前缀哈希值,即 h 数组,可以 $O(1)$ 的时间复杂度算出任意一个子串的哈希值。

   如果我们已知字符串 S 的 Hash 值为 H(S),字符串 S+T 的 Hash 值为 H(S+T), 则:H(T) = H(S + T) - H(S) * p^length(T)

   举个例子: 我们知道 hash(abcd) 的哈希值为 $2282810$,hash(ab) 的哈希值为 $133$,想求 hash(cd) 的哈希值就为: $2282810 - 133\ \times 131^2 = 2282810 - 133 \times 11716 = 2282810 - 2282413 = 397$。

   为了方便,可以开一个数组 $p$ 来记录 p^length(T),即 $p$ 的多少次方。

   具体的看一道例题:

   给定一个长度为 $n$ 的字符串,再给定 $m$ 个询问,每个询问包含四个整数 $l1,r1,l2,r2$,请你判断 $[l1,r1]$ 和 $[l2,r2]$ 这两个区间所包含的字符串子串是否完全相同。

   因为字符串中包含大小写英文字母和数字,所以我们把字符的 value 值设置为字符的 ASCII 码。

const int N = 1e5 + 10, P = 131;

typedef unsigned long long ULL;

ULL n, m, p[N], h[N];
char str[N];

ULL get(int l, int r)
{
    return h[r] - h[l - 1] * p[r - l + 1]; // 推出来的公式 2
}

int main()
{
    cin >> n >> m >> str + 1;
    
    p[0] = 1;  // p 的 0 次方为 1
    for (int i = 1; i <= n; i ++ )
    {
        h[i] = h[i - 1] * P + (int)str[i];  // 推出来的公式 1, value 为字符的 ASCII
        p[i] = p[i - 1] * P;
    }
    
    // for (int i = 1; i <= n; i ++ )
    // {
    //     cout << p[i] << ' '; // p 的多少次方
    //     cout << h[i] << ' '; // 前缀哈希值
    // }
    // cout << endl;
    
    while (m -- )
    {
        int l1, r1, l2, r2;
        cin >> l1 >> r1 >> l2 >> r2;
        cout << (get(l1, r1) == get(l2, r2) ? "Yes\n" : "No\n");
    }
    
    return 0;
}


致读者: 小时百科一直以来坚持所有内容免费无广告,这导致我们处于严重的亏损状态。 长此以往很可能会最终导致我们不得不选择大量广告以及内容付费等。 因此,我们请求广大读者热心打赏 ,使网站得以健康发展。 如果看到这条信息的每位读者能慷慨打赏 20 元,我们一周就能脱离亏损, 并在接下来的一年里向所有读者继续免费提供优质内容。 但遗憾的是只有不到 1% 的读者愿意捐款, 他们的付出帮助了 99% 的读者免费获取知识, 我们在此表示感谢。

                     

友情链接: 超理论坛 | ©小时科技 保留一切权利