力扣336.回文对 ——字符串哈希

以此题正式学习字符串哈希，要理解并背过

字符串哈希
(1) 把字符换设想成一个P进制的数
将字符串看成P进制数，P的经验值是131或13331，取这两个值的冲突概率低
对于整数132
1∗102+3∗10+2∗1001∗102+3∗10+2∗100
对于字符串abcde
a×P4+b×P3+c×P2+d×P1+e×P0a×P4+b×P3+c×P2+d×P1+e×P0
(2) 为什么使用unsigned long long
如果用上述P进制来存储字符串的哈希值，存在指数爆炸的情况，超出范围，而unsigned long long会将超出的部分会自动削减掉，就相当于了取模的操作，所以用这种操作来简化取模操作。取模的数用2^64，这样直接用unsigned long long存储，溢出的结果就是取模的结果。
(3) get(int l , int r)函数：得到指定范围L——R的字符串的哈希值
用进制运算，对于123456为例，要取得的456的哈希值需要以下操作：
已知L指向4 R指向6，咱需要得到L-1的哈希值即为123000，用123456 - 123000即可得到456的哈希值。

typedef unsigned long long ULL;
const int P = 131;
ULL h[N], p[N]; // h[k]存储字符串前k个字母的哈希值, p[k]存储 P^k mod 2^64
 
// 计算子串str[l~r]的哈希值,l和r范围为1~n
ULL get(int l, int r)
{
    return h[r]-h[l-1]*p[r-l+1];
}

//对p h数组初始化
p[0]=1;
for(int i=1;i<=n;i++)
{
    h[i]=h[i-1] *P +str[i];
    p[i]=p[i-1] *P;
}

此题代码解法

typedef unsigned long long ULL;   //为了节省时间，用ULL,且超过2^64会自动取模
const int N=310,P=131;     //数学里用131  13331比好好，不容易发生哈希冲突
ULL p[N];  // p[k]存储 P^k mod 2^64
class Solution {
public:
    //可以用字符串来写，也可以用字符串哈希来节省空间
 
    vector>h1,h2; //h[k]存储字符串前k个字母的哈希值    h1存放逆向，h2是正序
    ULL get(vector&h,int l,int r)   //函数计算 h数组里[l,r]的哈希值
    {
        return h[r]-h[l-1]*p[r-l+1];
    }
 
    vectorint>> palindromePairs(vector& words) {
        p[0]=1;
        for(int i=1;i//初始化p数组
        {
            p[i]=p[i-1]*P;
        }
 
        for(int i=0;isize();i++)
        {
            int n=words[i].size();
            vectora(1),b(1);   //使下标从1开始
            for(int j=1;j<=n;j++) a.push_back(a.back()*P+words[i][j-1]);  //以此得逆序哈希
            for(int j=n;j;j--) b.push_back(b.back()*P+words[i][j-1]);  //得出正序哈希
            h1.push_back(a);
            h2.push_back(b);
        }
 
 
 
        unordered_mapint>hash;    //key为字符串哈希值，value是当前字符串在字符串数组的下标
        for(int i=0;isize();i++)
        {
            hash[get(h2[i],1,words[i].size())]=i;    
        }
        vectorint>>res;
        for(int i=0;isize();i++)
        {
            int n=words[i].size();
            for(int j=0;j<=n;j++)
            {
                auto left=get(h1[i],1,j),right=get(h1[i],j+1,n);   //h数组下标是从0开始   a,b数组下标是从1开始
                //有三种情况，一种是第一个单词大于等于第二个，此时前缀和第二个单词回文，后缀自己回文
                //第二种情况是第一个单词小于等于第二个，此时前缀和第二个单词后缀回文，第二个单词前缀自己回文
                if(right==get(h2[i],1,n-j)&&hash.count(left)&&hash[left]!=i) res.push_back({i,hash[left]});
                if(left==get(h2[i],n-j+1,n)&&hash.count(right)&&hash[right]!=i&&words[i].size()!=words[hash[right]].size())
                {
                    res.push_back({hash[right],i});
                }
            }
        }
        return res;
    }
};