@rainkaras
@sustainer123
@DJkdfhsina宝
@刷题帮
Rolling Hash 的优点是快
缺点是靠赛 而且很毒瘤
Rolling Hash处理字串的时候很方便
可以用O(1)的时间来比对两个字串
甚至是分段比对也可以
原理自己查
大概就是用一只*base之后做出当前字串的hash value
然后把这个当前缀和的阵列
然后利用这个阵列快速找出每个地方的Rolling Hash 值
也就是说有可能有字符撞到hash value的情况
这种情况你可以改用更大的base
或是用两个不同的base判断两次
或是在遇到值的时候O(n)检查
https://leetcode.com/problems/count-prefix-and-suffix-pairs-ii/
题目:
给你一堆字串
请问 a字串 同时是 b字串 的前缀和后缀的组合有多少种
思路:
把每个字串都弄出Rolling Hash 值之后插入unordered map
记录他的值跟数量
然后要增加合法配对的时候
要判断每个前缀后缀是否相等
然后去前面找当前的hash值
姆咪
函式模板本体 :
class RollingHash {
long long mod, base;
vector<long long> h, p;
public:
template<class T>
RollingHash(const T& data, long long mod, long long base): mod(mod), base(ba
se), h{0}, p{1} {
for(auto& d: data) {
h.push_back((h.back() * base + d) % mod);
p.push_back(p.back() * base % mod);
}
}
long long hash(int l, int r) {
return (h[r+1] - h[l] * p[r-l+1] % mod + mod) % mod;
}
};
class Solution {
public:
long long countPrefixSuffixPairs(vector<string>& words)
{
int n = words.size();
unordered_map<long long,int> haha;
long long res = 0 ;
for(int i = 0 ; i < n ; i ++)
{
RollingHash rh(words[i],1e9+7,1104);
// cout << " ===== " << rh.hash(0,words[i].size()-1) << endl;
for(int j = 0 ; j < words[i].size() ; j ++)
{
// cout << " ===== " << rh.hash(0,j) << endl;
if(rh.hash(0,j) == rh.hash(words[i].size()-1-j,words[i].size()-1
))res += haha[rh.hash(0,j)];
// if(rh.hash(0,j) != rh.hash(words[i].size()-1-j,words[i].size(
)-1))continue;
// haha[rh.hash(0,j)]++;
}
haha[rh.hash(0,words[i].size()-1 )]++;
// for(auto k : haha)
// {
// cout << k.first << " " << k.second << endl;
// }
}
return res;
}
};
```