当前位置:网站首页># 2156. 查找给定哈希值的子串-后序遍历
# 2156. 查找给定哈希值的子串-后序遍历
2022-07-04 21:23:00 【Mr Gao】
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;
}
边栏推荐
猜你喜欢
Bookmark
gtest从一无所知到熟练使用(3)什么是test suite和test case
Sorting and sharing of selected papers, systems and applications related to the most comprehensive mixed expert (MOE) model in history
解读创客教育中的各类智能化组织发展
Arcgis 10.2.2 | arcgis license server无法启动的解决办法
Keep on fighting! The city chain technology digital summit was grandly held in Chongqing
MongoDB聚合操作总结
Why do you have to be familiar with industry and enterprise business when doing Bi development?
CloudCompare&Open3D DBSCAN聚类(非插件式)
改善机器视觉系统的方法
随机推荐
File read write
Keep on fighting! The city chain technology digital summit was grandly held in Chongqing
Redis bloom filter
TCP协议三次握手过程
【C語言】符號的深度理解
哈希表(Hash Tabel)
How is the entered query SQL statement executed?
Analysis of maker education technology in the Internet Era
旋变串判断
Daily question-leetcode556-next larger element iii-string-double pointer-next_ permutation
做BI开发,为什么一定要熟悉行业和企业业务?
Maya lamp modeling
QT—绘制其他问题
案例分享|金融业数据运营运维一体化建设
Super detailed tutorial, an introduction to istio Architecture Principle and practical application
flink1.13 sql基础语法(一)DDL、DML
Kubeadm初始化报错:[ERROR CRI]: container runtime is not running
Master the use of auto analyze in data warehouse
应用实践 | 蜀海供应链基于 Apache Doris 的数据中台建设
[buuctf.reverse] 151_ [FlareOn6]DnsChess