力扣2156.查找给定哈希值的子串
class Solution {
public:
string subStrHash(string s, int power, int modulo, int k, int hashValue) {
int n = s.size();
long long M = modulo,pk=1,hash = 0;
//预处理k个 并求出p^k-1
for(int i=n-1;i>=n-k;i--)
{
hash = ((long long)hash*power + (s[i] - 'a' + 1)) % M;
if(i != n-k) pk = (long long)pk*power%M;
}
int pos = -1;
if(hash == hashValue) pos = n-k;
for(int i=n-k-1;i>=0;i--)
{
//把右边高位减掉
hash = hash - (s[i+k] - 'a' + 1) * pk % M;
//防止hash减完成负数
hash = (hash + M) %M;
//整体左移(升高一位)
hash = hash * power % M;
//加上左边低位
hash = (hash + s[i]-'a'+1) % M;
if(hash == hashValue){
pos = i;
}
}
return s.substr(pos,k);
}
};