以此题正式学习字符串哈希，要理解并背过
字符串哈希
(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<vector<ULL>>h1,h2;?//h[k]存储字符串前k个字母的哈希值????h1存放逆向，h2是正序
????ULL?get(vector<ULL>&h,int?l,int?r)???//函数计算?h数组里[l,r]的哈希值
????{
????????return?h[r]-h[l-1]*p[r-l+1];
????}
????vector<vector<int>>?palindromePairs(vector<string>&?words)?{
????????p[0]=1;
????????for(int?i=1;i<N;i++)??//初始化p数组
????????{
????????????p[i]=p[i-1]*P;
????????}
????????for(int?i=0;i<words.size();i++)
????????{
????????????int?n=words[i].size();
????????????vector<ULL>a(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_map<ULL,int>hash;????//key为字符串哈希值，value是当前字符串在字符串数组的下标
????????for(int?i=0;i<words.size();i++)
????????{
????????????hash[get(h2[i],1,words[i].size())]=i;????
????????}
????????vector<vector<int>>res;
????????for(int?i=0;i<words.size();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;
????}
};