1 class Solution {
 2 public:
 3     typedef long long ll;
 4     string subStrHash(string s, int k, int mod, int len, int hashValue) {
 5         string ans="";
 6         int n=s.size();
 7         ll p[n+1],ha[n+1];
 8         p[0]=1%mod,ha[n]=0;
 9         for(int i=1;i<n;i++)p[i]=1ll*p[i-1]*k%mod;
10         for(int i=n-1;i>=0;i--)ha[i]=(1ll*ha[i+1]*k+(s[i]-'a'+1))%mod;
11         for(int i=0;i<n;i++)
12         {
13             if(i+len-1<n)      
14             if((ha[i]-ha[i+len]*p[len]%mod+mod)%mod==hashValue)return s.substr(i,len);
15         }
16         return ans;
17     }
18 };

 

class Solution {public:    typedef long long ll;    string subStrHash(string s, int k, int mod, int len, int hashValue) {        string ans="";        int n=s.size();        ll p[n+1],ha[n+1];        p[0]=1%mod,ha[n]=0;        for(int i=1;i<n;i++)p[i]=1ll*p[i-1]*k%mod;        for(int i=n-1;i>=0;i--)ha[i]=(1ll*ha[i+1]*k+(s[i]-'a'+1))%mod;        for(int i=0;i<n;i++)        {            if(i+len-1<n)                  if((ha[i]-ha[i+len]*p[len]%mod+mod)%mod==hashValue)return s.substr(i,len);        }        return ans;    }};