字符串哈希

                     

贡献者: 有机物

   字符串哈希和普通的哈希算法类似,字符串哈希是把一个很长的字符串变成一个整数,这样的好处是:如果想比较两个很长的字符串是否相等时,普通算法是遍历一遍整个字符串,如果其中一个字符串的字符和另一个字符串的字符不等,则两个字符串不一样。时间复杂度为 $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;
}

                     

© 小时科技 保留一切权利