＃ 2156. Find the substring of the given hash value - post order traversal

2156. Find the substring of the given hash value - After the sequence traversal

Given integer p and m , A length of k And subscript from 0 Starting string s The hash value of is calculated according to the following function ：

hash(s, p, m) = (val(s[0]) * p0 + val(s[1]) * p1 + ... + val(s[k-1]) * pk-1) mod m.

among val(s[i]) Express s[i] Subscript in the alphabet , from val(‘a’) = 1 To val(‘z’) = 26 .

Give you a string s And integer power,modulo,k and hashValue . Please return s in first The length is k Of Substring sub , Satisfy hash(sub, power, modulo) == hashValue .

The test data ensure that There is At least one such substring .

Substring Defined as a sequence of consecutive non null characters in a string .

Example 1：

Input ：s = “leetcode”, power = 7, modulo = 20, k = 2, hashValue = 0
Output ：“ee”
explain ：“ee” The hash value of hash(“ee”, 7, 20) = (5 * 1 + 5 * 7) mod 20 = 40 mod 20 = 0 .
“ee” It's a length of 2 The first hash value of is 0 The string of , So we go back to “ee” .

Example 2：

Input ：s = “fbxzaad”, power = 31, modulo = 100, k = 3, hashValue = 32
Output ：“fbx”
explain ：“fbx” The hash value of hash(“fbx”, 31, 100) = (6 * 1 + 2 * 31 + 24 * 312) mod 100 = 23132 mod 100 = 32 .
“bxz” The hash value of hash(“bxz”, 31, 100) = (2 * 1 + 24 * 31 + 26 * 312) mod 100 = 25732 mod 100 = 32 .
“fbx” It's a length of 3 The first hash value of is 32 The string of , So we go back to “fbx” .
Be careful ,“bxz” The hash value of is also 32 , But it is better than... In the string “fbx” Later .

source ： Power button （LeetCode）
link ：https://leetcode.cn/problems/find-substring-with-given-hash-value
Copyright belongs to the network . For commercial reprint, please contact the official authority , Non-commercial reprint please indicate the source .

The solution code is as follows , This question is for c The language is not very friendly , It takes a lot of work , But take your time , The main idea of solving the problem is to start traversing the tail , Need some mathematical derivation

long long pend;
int f(char *s,int index,int k,int modulo,int power){
    
    int sum=0;
    int i;
    long long p=1;
    for(i=index;i<=k+index-1;i++){
    
    // printf("%d ||",p);
        sum=(sum+(s[i]-'a'+1)*p)%modulo;
        if(i==k+index-1){
    
            pend=p;
        }
        p=(p*power)%modulo;
    }
  

return sum%modulo;
}


char * subStrHash(char * s, int power, int modulo, int k, int hashValue){
    
    long long i;

     pend=1;
    long long   end=f(s,strlen(s)-k,k,modulo,power);
 
  int end_index;
    if(end==hashValue){
    

        
            end_index=strlen(s)-k;
    }
  // printf("%d ",end);

    for(i=strlen(s)-k-1;i>=0;i--){
    

      if(end<pend*(s[i+k]-'a'+1)){
    
          end=end+modulo;
      }
        long long  z=(end-pend*(s[i+k]-'a'+1)%modulo)%modulo;
      long long  re=(z*power+(s[i]-'a'+1))%modulo;
      end=re;

      if(re==hashValue){
    
          end_index=i;
        

      }
    }

    // for(i=0;i<=strlen(s)-k;i++){
    
    // // printf("%d ",i);
    // // printf("%d ",f(s,i,k,modulo,power));
    // if(f(s,i,k,modulo,power)==hashValue){
    
    // s[i+k]='\0';
    // return s+i;
    // }
    // }
       s[end_index+k]='\0';
          return s+end_index;

}