当前位置:网站首页># 2156. Find the substring of the given hash value - post order traversal
# 2156. Find the substring of the given hash value - post order traversal
2022-07-04 22:02:00 【Mr Gao】
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;
}
边栏推荐
- WebGIS framework -- kalrry
- Relational database
- 做BI开发,为什么一定要熟悉行业和企业业务?
- 更强的 JsonPath 兼容性及性能测试之2022版(Snack3,Fastjson2,jayway.jsonpath)
- 2022 version of stronger jsonpath compatibility and performance test (snack3, fastjson2, jayway.jsonpath)
- 淘宝商品评价api接口(item_review-获得淘宝商品评论API接口),天猫商品评论API接口
- How was MP3 born?
- HDU - 1078 fatmouse and cheese (memory search DP)
- 哈希表(Hash Tabel)
- Shutter textfield example
猜你喜欢
Operation of adding material schedule in SolidWorks drawing
PMO:比较25种分子优化方法的样本效率
【活动早知道】LiveVideoStack近期活动一览
使用 BlocConsumer 同时构建响应式组件和监听状态
QT—双缓冲绘图
Case sharing | integrated construction of data operation and maintenance in the financial industry
Shutter textfield example
Arcgis 10.2.2 | arcgis license server无法启动的解决办法
Why do you have to be familiar with industry and enterprise business when doing Bi development?
TCP三次握手,四次挥手,你真的了解吗?
随机推荐
什么是商业智能(BI),就看这篇文章足够了
Learning breakout 3 - about energy
HDU - 2859 Phalanx(DP)
How much is the minimum stock account opening commission? Is it safe to open an account online
Cadre WebGIS - kalrry
Go language loop statement (3 in Lesson 10)
历史最全混合专家(MOE)模型相关精选论文、系统、应用整理分享
能源势动:电力行业的碳中和该如何实现?
How was MP3 born?
EhLib 数据库记录的下拉选择
智洋创新与华为签署合作协议,共同推进昇腾AI产业持续发展
VIM from dislike to dependence (23) -- the last gossip
【LeetCode】17、电话号码的字母组合
Redis03 - network configuration and heartbeat mechanism of redis
El tree combined with El table, tree adding and modifying operations
哈希表(Hash Tabel)
【C語言】符號的深度理解
Flink1.13 SQL basic syntax (I) DDL, DML
【C语言进阶篇】数组&&指针&&数组笔试题
[public class preview]: basis and practice of video quality evaluation