Re: [閒聊] 每日leetcode
題目
幾種配對其中一個字串是另一個字串的前綴+後綴
思路
用Rolling Hash來配對
```cpp
class RollingHash {
long long mod, base;
vector<long long> h, p;
public:
template<class T>
RollingHash(){}
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:
int countPrefixSuffixPairs(vector<string>& words)
{
int n = words.size();
vector<RollingHash> rhs;
for(int i = 0 ; i < n ; i ++)
{
RollingHash rh(words[i],1e9+7,931104);
rhs.push_back(rh);
}
int res = 0 ;
for(int i = 0 ; i < n ; i ++)
{
int len1 = words[i].size();
for(int j = i+1 ; j < n ; j ++)
{
int len2 = words[j].size();
if(len1>len2)continue;
if( rhs[j].hash(0,len1-1) == rhs[i].hash(0,len1-1) && rhs[j].has
h(len2-len1,len2-1) == rhs[i].hash(0,len1-1) )res ++;
}
}
return res;
}
};```
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 125.228.169.39 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Marginalman/M.1736315992.A.883.html
推
01/08 15:40,
11月前
, 1F
01/08 15:40, 1F
→
01/08 15:40,
11月前
, 2F
01/08 15:40, 2F
討論串 (同標題文章)
完整討論串 (本文為第 1254 之 1554 篇)：