LC困难题 滚动Hash

技巧大法

给定整数 p 和 m ，一个长度为 k 且下标从 0 开始的字符串 s 的哈希值按照如下函数计算：

hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.
其中 val(s[i]) 表示 s[i] 在字母表中的下标，从 val('a') = 1 到 val('z') = 26 。

给你一个字符串 s 和整数 power，modulo，k 和 hashValue 。请你返回 s 中 第一个 长度为 k 的 子串 sub ，满足 hash(sub, power, modulo) == hashValue 。

测试数据保证一定 存在 至少一个这样的子串。

子串 定义为一个字符串中连续非空字符组成的序列。

示例 1：

输入：s = "leetcode", power = 7, modulo = 20, k = 2, hashValue = 0
输出："ee"
解释："ee" 的哈希值为 hash("ee", 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 。
"ee" 是长度为 2 的第一个哈希值为 0 的子串，所以我们返回 "ee" 。
示例 2：

输入：s = "fbxzaad", power = 31, modulo = 100, k = 3, hashValue = 32
输出："fbx"
解释："fbx" 的哈希值为 hash("fbx", 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 。
"bxz" 的哈希值为 hash("bxz", 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 。
"fbx" 是长度为 3 的第一个哈希值为 32 的子串，所以我们返回 "fbx" 。
注意，"bxz" 的哈希值也为 32 ，但是它在字符串中比 "fbx" 更晚出现。

class Solution {
public:
    string subStrHash(string s, int power, int modulo, int k, int hashValue) {
        
        string ans="";
        
        //求出power的n次方%modulo的窗口值 
        vector<int> _mi=mi(power,modulo,k);
        int _cycle_mod_size=_mi.size();
        
        //窗口大小为k的值
        long long pre=0LL;
        int mod=0;
        for(int i=0;i<k;i++){
            int factor=(s[i]-'a')+1;
            if(i==0){
                mod+=factor%modulo;
            }
            else{
                int _my=factor*_mi[(i-1)%_cycle_mod_size];
                mod+=(_my)%modulo;
            }
            
          if(i>=1){
                pre+=((factor)*power);
            }
            ans.push_back(s[i]);
        }
        
        if(mod%modulo==hashValue){
            return ans;
        }
        //前k个字符的hash取模值
        int _window_idx=1;
       
        
        for(int i=k;i<s.size();i++,_window_idx++){
             int factor=(s[i]-'a')+1;
             int pre_factor=1+(s[_window_idx]-'a');
             ans.erase(0,1);
            
            
             ans.push_back(s[i]);
             int _my=factor*_mi[(i-k+1)%_cycle_mod_size];
            
             //[1,3*2,5X2*2,7X2*2*2]
             mod=mod-((pre/power)%modulo);
             mod-=pre_factor;
             mod+=_my;
            
            pre=pre+(factor*power)-pre_factor;
            mod=abs(mod)%modulo;
            
           if(mod==hashValue){    
             return ans;
            }
            
            //
        }

           return ans;
           }
    
    
    vector<int> mi(long long P,long long M,int k){
        vector<int> ans;
        long long mod=P%M;
        if(mod==0){
            
            return {0};
        }
   
        int left=-1;
        ans.push_back(mod);
        long long P_X=P;

        for(int i=1;left!=ans[0]&&i<=k+1;i++){
            P_X=P_X*P;
            if(left==ans[0])
                break;
              left=P_X%M;
          if(left!=ans[0])
           ans.push_back(left);
                    
        }
        return ans;
        
    }
    
   

    
};