Re: [演算法] 每日leetcode - Rolling Hash
@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;
}
};
```
--
邊版的小母雞 — fuckchicken
https://i.imgur.com/wglAuYR.jpg
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 49.216.27.220 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1734441686.A.724.html
→
12/17 21:22,
1年前
, 1F
12/17 21:22, 1F