力扣2156.查找给定哈希值的子串

力扣2156.查找给定哈希值的子串

• rolling hash：求带权的值 左边是高位 右边是低位

  • 本题要求左边低位 只要反向求即可

•   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);
        }
    };