题目
几种配对其中一个字串是另一个字串的前缀+后缀
思路
用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;
}
};```