字符串哈希

一时失言乱红尘 2022-04-22 14:02 262阅读 0赞

下面介绍的字符串Hash函数把一个任意长度的字符串映射成一个非负整数，并且其冲突概率几乎为零。

**取一固定值P，把字符串看作P进制数，并分配一个大于0的数值，代表每种字符。** 一般来说，我们分配的数值都远小于P。例如，对于小写字母构成的字符串，可以令 a = 1 , b = 2 , . . . , z = 26 。 a=1,b=2,...,z=26。 a=1,b=2,...,z=26。 **取一固定值M，求出该P进制数对M的余数，作为该字符串的Hash值。**

一般来说，我们取P=131或P=13331，此时Hash值产生冲突的概率极低，只要Hash值相同，我们就可以认为原字符串是相等的。通常我们取 M = 2 64 M=2^\{64\} M=264，即**直接使用unsigned long long类型**存储这个Hash值，在计算时不处理算术溢出问题，产生溢出时相当于自动对 2 64 2^\{64\} 264取模，这样可以避免低效的取模运算。

除了在及特殊构造的数据上，上述Hash很难产生冲突，一般情况下上述Hash算法完全可以出现在题目的标准解答中。我们还可以多取一些恰当的P和M值（例如大质数），多进行几组Hash运算，当结果都相同时才认为原字符串相等，就更难以构造出使这个Hash产生错误的数据。

**对字符串的各种操作，都可以直接对P进制数进行算数运算反映到Hash值上。**

如果我们已知字符串S的Hash值为H(S)，那么在S后添加一个字符c构成的新字符串S+c的Hash值就是 H ( S + c ) = ( H ( S ) ∗ P + v a l u e \[ c \] ) m o d &ThinSpace;&ThinSpace; M H(S+c) = (H(S)\*P +value\[c\]) \\mod M H(S\+c)=(H(S)∗P\+value\[c\])modM。其中乘P就相当于P进制下的左移运算，value\[c\]是我们的为c选定的代表数值。

如果我们已知字符串S的Hash值为H(S)，字符串S+T的Hash值为 H ( S + T ) H(S+T) H(S\+T)，那么字符串T的Hash值 H ( T ) = ( H ( S + T ) − H ( S ) ∗ P l e n g t h ( T ) ) m o d &ThinSpace;&ThinSpace; M H(T) = (H(S+T)-H(S)\*P^\{length(T)\})\\mod M H(T)=(H(S\+T)−H(S)∗Plength(T))modM。这就相当于通过P进制下在S后边补0的方式，把S左移到与S+T的左端对其，然后二者相减就得到了H(T)。

> 例如，S=“abc”，c=“d”，T=“xyz”，则：  
> S表示为P进制数: 1 2 3  
>  H ( S ) = 1 ∗ P 2 + 2 ∗ P + 3 H(S) = 1\*P^2+2\*P+3 H(S)=1∗P2\+2∗P\+3  
>  H ( S + c ) = 1 ∗ P 3 + 2 ∗ P 2 + 3 ∗ P + 4 = H ( S ) ∗ P + 4 H(S+c) = 1\*P^3+2\*P^2+3\*P+4=H(S)\*P+4 H(S\+c)=1∗P3\+2∗P2\+3∗P\+4=H(S)∗P\+4  
> S+T表示为P进制数: 1 2 3 24 25 26  
>  H ( S + T ) = 1 ∗ P 5 + 2 ∗ P 4 + 3 ∗ P 3 + 24 ∗ P 2 + 25 ∗ P + 26 H(S+T) = 1\*P^5+2\*P^4+3\*P^3+24\*P^2+25\*P+26 H(S\+T)=1∗P5\+2∗P4\+3∗P3\+24∗P2\+25∗P\+26  
> S在P进制下左移length(T) 位: 1 2 3 0 0 0  
> 二者相减就是T表示为P进制数: 24 25 26  
>  H ( T ) = H ( S + T ) − ( 1 ∗ P 2 + 2 ∗ P + 3 ) ∗ P 3 = 24 ∗ P 2 + 25 ∗ P + 26 H(T)=H(S+T)-(1\*P^2+2\*P+3)\*P^3=24\*P^2+25\*P+26 H(T)=H(S\+T)−(1∗P2\+2∗P\+3)∗P3=24∗P2\+25∗P\+26

根据上面两种操作，我们可以通过**O(N)的时间预处理字符串所有前缀Hash值，并在O(1)的时间内查询它的任意子串的Hash值。**

#### 例题：兔子与兔子 CH1401 ####

很久很久以前，森林里住着一群兔子。有一天，兔子们想要研究自己的DNA序列。我们首先选取一个好长好长的DNA序列（小兔子是外星生物，DNA序列可能包含26个小写英文字母），然后我们每次选择两个区间，询问如果用两个区间里的DNA序列分别生产出来两只兔子，这两只兔子是否一模一样。注意两只兔子一模一样只可能是它们的DNA序列一模一样。 1 ≤ l e n g t h ( s ) , Q ≤ 1 0 6 1\\le length(s),Q \\le 10^6 1≤length(s),Q≤106

记我们选取的DNA序列为S，根据我们刚才提到的字符串Hash算法，设 F \[ i \] F\[i\] F\[i\]表示前缀子串S\[1~i\]的Hash值，有 F \[ i \] = F \[ i − 1 \] ∗ 131 + ( S \[ i \] − " a " + 1 ) 。 F\[i\]=F\[i-1\]\*131+(S\[i\]-"a"+1)。 F\[i\]=F\[i−1\]∗131\+(S\[i\]−"a"\+1)。  
于是可以得到任一区间\[l,r\]的Hash值为 F \[ r \] − F \[ l − 1 \] ∗ 13 1 r − l + 1 F\[r\]-F\[l-1\]\*131^\{r-l+1\} F\[r\]−F\[l−1\]∗131r−l\+1。当两个区间的Hash值相同时，我们就认为对应的两个子串相等。整个算法的时间复杂度为 O ( ∣ S ∣ + Q ) 。 O(|S|+Q)。 O(∣S∣\+Q)。

char s[1000010];
    unsigned long long f[1000010],p[1000010];
    int main(){ 
        scanf("%s",s+1);
        int n = strlen(s+1),q; cin>>q;
        p[0] = 1; //131^0
        for (int i=1; i<=n; ++i){ 
            f[i] = f[i-1] * 131 + (s[i]-'a'+1); //hash of 1~i
            p[i] = p[i-1] * 131; // 131^i
        }
        for (int i = 1; i <= q; ++i){ 
            int l1,r1,l2,r2;
            scanf("%d%d%d%d", &l1, &r1, &l2, &r2);
            if (f[r1]-f[l1-1]*p[r1-l1+1] == //hash of l1~r1
                f[r2]-f[l2-1]*p[r2-l2+1]){   //hash of l2~r2
                puts("yes");
            } else puts("no");
        }
    }

#### 【例题】Palindrome \[poj3974\] ####

如果一个字符串正着读和倒着读是一样的，则称它是回文的。给定一个长度为N的字符串S，求它的最长回文子串。

写几个回文串观察他们的性质，我们可以发现回文串分为两类：

1.  奇回文串A\[1~M\]，长度M为奇数，并且A\[1~M/2+1\]=reverse(A\[M/2+1~M\])，它的中心点是一个字符。
2.  偶回文串B\[1~M\]，长度M为偶数，且B\[1~M/2\]=reverse(B\[M/2+1~M)，它的中心点是两个字符之间的夹缝。

于是在本题中，我们可以枚举S的回文子串的中心位置i=1~N，看从这个中心位置出发向左右两侧最长可以扩展出多长的回文串。也就是说：

1.  求出一个最大的整数p使得S\[i-p~i\]=reverse(S\[i~i+p\])，那么以i为中心的最长奇回文子串的长度就是2\*p+1。
2.  求出一个最大的整数q使得S\[i-q~i-1\] = reverse(S\[i~i+q-1\])，那么以i-1和i之间的夹缝为中心的最长偶回文子串的长度就是2\*q。

![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlYXJsZXNzeGpkeA_size_16_color_FFFFFF_t_70]  
根据上一道题目，我们已经知道在O(N)预处理前缀Hash值后，可以O(1)计算任意子串的Hash值。类似的，我们可以倒着做一遍预处理，就可以O(1)计算任意子串倒着读的Hash值。于是我们可以对p和q进行二分答案，用Hash值O(1)比较一个正着读的子串和一个倒着读的子串是否相等，从而在O(logN)时间内求出最大的p和q。在枚举过程的所有中心位置对应的奇、偶回文子串长度中取max就是整道题目的答案，时间复杂度为O(NlogN)。  
有一个名为Manacher的算法可以O(N)求解该问题，感兴趣的读者可以自行查阅相关资料。

#### 【例题】后缀数组 CH1402 ####

后缀数组(SA)是一种重要的数据结构，通常使用倍增或者DC3算法实现，这超出了我们的讨论范围。在本题中，我们希望使用快排、Hash与二分实现一个简单的 O ( n l o g 2 n ) O(nlog^2n) O(nlog2n)的后缀数组求法。详细地说，给定一个长度为n的字符串S（下标0~n-1），我们可以用整数k(0<=k<n)表示字符串S的后缀S(K~n-1)。把字符串S的所有后缀按照字典序排列，排名为i的后缀记为SA\[i\]。额外的，我们考虑排名为i的后缀与排名为i-1的后缀，把二者的最长公共前缀的长度记为Height\[i\]。我们的任务就是求出SA与Height这两个数组。

S的所有后缀的总长度在 O ( n 2 ) O(n^2) O(n2)级别，如果我们直接对这n个后缀进行快排，对于两个字符串的大小比较采取逐字符扫描的方式，最坏情况下时间复杂度将达到 O ( n 2 l o g n ) O(n^2logn) O(n2logn)。  
在上一道题目中，我们已经知道如何求一个字符串的所有前缀Hash值，并进一步在O(1)的时间内查询任意一个区间子串的Hash值。所有在快速排序需要比较两个后缀p和q时，我们就可以使用二分法，每次二分时利用Hash值O(1)地比较S\[p~p+mid-1\]与S\[q~q+mid-1\]这两段是否相等，最终求出S\[p~n\]与S\[q~n\]的最长公共前缀的长度，记为len。于是S\[p+len\]和S\[q+len\]就是这两个后缀第一个不相等的位置，直接比较这两个字符的大小就可以确定S\[p~n\]与S\[q~n\]的大小关系。从而每次比较的复杂度就是 O ( log ⁡ n ) O(\\log n) O(logn)，整个快排求出SA数组的过程的复杂度就是 O ( n log ⁡ 2 n ) O(n\\log^2 n) O(nlog2n)。在排序完成后，我们对于每对排序相邻的后缀执行与上述相同的二分过程，就可以求出Height数组了。

#### 小结 ####

Hash在处理字符串子串是否相等的时候比较高效，但如果只是比较后缀或者前缀的话，还是用Trie树更准确。

本文大部分摘自《算法竞赛进阶指南》

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L2ZlYXJsZXNzeGpkeA_size_16_color_FFFFFF_t_70]: /images/20220422/834f76c412fe40eb8e93e15a30713f15.png