[数据结构与算法]# 2156. 查找给定哈希值的子串-后序遍历

2156. 查找给定哈希值的子串-后序遍历

给定整数 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” 更晚出现。

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/find-substring-with-given-hash-value
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

解题代码如下，这题对于c语言不是很友好，做起来很费事，但是大家慢慢来，解题思路主要是尾部开始遍历，需要一些数学推导

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;

}