字符串哈希

使用固定的流程，将任意长度的字符串映射成为一个数字—-哈希值，并且相同的字符串拥有相同的哈希值。

对字符串进行哈希映射后，可以在$O(1)$的时间内判断该字符串的任意子串是否相等。

哈希过程：

1.选取一个基数base表示是几进制数，一般选base = 131, 或者 base = 13331，这样产生哈希冲突的概率极低。

2.通常使用long存储哈希值，当计算出的哈希值超过long范围时，产生的溢出相当于直接做了取模运算，从而可以在计算时不使用取模运算。(取模值M=$2^{64}-1$)

3.运算法则：

• 已知字符串S的哈希值H(S)，那么在其后面添加一个字符c，得到的字符串的哈希值为：$H(S+c)=(H(S)*base+value(c))\%M$​​，该计算相当于在base进制下进行左移。

  可以看成是：从后往前计算base进制数的过程

• 已知字符串S+T的哈希值为H(S+T)，S的哈希值为H(S)，那么T的哈希值为：$H(T)=(H(S+T)-H(S)*base^{len(T)})\%M$​，该计算相当于在base进制下，将H(S)左移补零，使得与`H(S+T)左端对齐再相减。

4.计算技巧：在计算前缀哈希值时，可以顺便计算$base^{n}$这样就省去了独立计算$base^{len(T)}$的时间。

题目：

1392. 最长快乐前缀

1044. 最长重复子串

5994. 查找给定哈希值的子串

1316. 不同的循环子字符串

2223. 构造字符串的总得分和

214. 最短回文串

class Solution {
    
    public String longestPrefix(String s) {
        int n = s.length();
        int base = 131; // 表示131进制，（p = 13331）
        long[] hash = new long[n + 1]; // 0～i前缀字符串的哈希值
        long[] p = new long[n + 1]; // 保存base的几次方
        p[0] = 1; // base零次方等于1
        // 计算前缀哈希值
        for (int i = 1; i <= n; i++) {
            // 计算哈希值：隐含取模 Long.MAX_VALUE
            hash[i] = hash[i - 1] * base + s.charAt(i - 1) - 'a';
            // 保存base的i次方值，方便计算任意子串的哈希值
            p[i] = p[i - 1] * base;
        }
        // 计算后缀哈希值
        for (int i = n - 1; i >= 1; i--) {
            long pre = hash[i]; // H(S)
            // H(T) = (H(S+T) - H(S) * base ^ len(T))
            long back = hash[n] - hash[n - i] * p[i]; // 后缀哈希值
            // 前后缀哈希值相等，可以认为两字符串相等
            if (pre == back) {
                return s.substring(0, i);
            }
        }
        return "";
    }
}

利用质数计算字符串哈希值

将每个字母分别映射到一个质数，计算哈希值时使用乘法，由于乘法满足交换率，字母映射到质数，所以不互为「变位词」的字符串计算得到的哈希值是不一样的。

🐷：只适用于字符串长度较小的case

int[] hash = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 
                        47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101};
long hashCode = 1l;
for (int i = 0; i < s.length(); i++) {
    hashCode *= hash[s.charAt(i) - 'a'];
}