1967. 作为子字符串出现在单词中的字符串数目字符串模式匹配-kmp算法和kmp优化算法(双百代码)
2023-09-14 09:06:49 时间
1967. 作为子字符串出现在单词中的字符串数目字符串模式匹配-kmp算法和kmp优化算法(双百代码)
给你一个字符串数组 patterns 和一个字符串 word ,统计 patterns 中有多少个字符串是 word 的子字符串。返回字符串数目。
子字符串 是字符串中的一个连续字符序列。
示例 1:
输入:patterns = [“a”,“abc”,“bc”,“d”], word = “abc”
输出:3
解释:
- “a” 是 “abc” 的子字符串。
- “abc” 是 “abc” 的子字符串。
- “bc” 是 “abc” 的子字符串。
- “d” 不是 “abc” 的子字符串。
patterns 中有 3 个字符串作为子字符串出现在 word 中。
示例 2:
输入:patterns = [“a”,“b”,“c”], word = “aaaaabbbbb”
输出:2
解释:
- “a” 是 “aaaaabbbbb” 的子字符串。
- “b” 是 “aaaaabbbbb” 的子字符串。
- “c” 不是 “aaaaabbbbb” 的字符串。
patterns 中有 2 个字符串作为子字符串出现在 word 中。
示例 3:
输入:patterns = [“a”,“a”,“a”], word = “ab”
输出:3
解释:patterns 中的每个字符串都作为子字符串出现在 word “ab” 中。
对于这个题目,很多人可能就会暴力,匹配,但是,暴力匹配终究不是好的办法,时间开销太大,这里给出kmp算法和mmp优化算法,感兴趣可以学习一下,这个算法非常帮,在考研和工作中都是十分常见的:
kmp算法:
bool kmp_pattern_match(char *s,char *word,int lenw){
int lens=strlen(s);
int next[lens];
int i=0,k=-1;
next[0]=-1;
while(i<lens-1){
if(k==-1||s[i]==s[k]){
k++;
i++;
next[i]=k;
}
else{
k=next[k];
}
}
int is=0,iword=0;
while(is<lens&&iword<lenw){
if(is==-1||s[is]==word[iword]){
is++;
iword++;
}
else{
is=next[is];
}
}
if(is==lens){
return true;
}
else{
return false;
}
}
int numOfStrings(char ** patterns, int patternsSize, char * word){
int count=0;
int lenw=strlen(word);
for(int i=0;i<patternsSize;i++){
if(kmp_pattern_match(patterns[i],word,lenw)){
count++;
}
}
return count;
}
kmp优化算法
bool kmp_pattern_match(char *s,char *word,int lenw){
int lens=strlen(s);
int next[lens];
int i=0,k=-1;
next[0]=-1;
while(i<lens-1){
if(k==-1||s[i]==s[k]){
k++;
i++;
if(s[i]==s[k]){
next[i]=next[k];
}
else{
next[i]=k;
}
}
else{
k=next[k];
}
}
int is=0,iword=0;
while(is<lens&&iword<lenw){
if(is==-1||s[is]==word[iword]){
is++;
iword++;
}
else{
is=next[is];
}
}
if(is==lens){
return true;
}
else{
return false;
}
}
int numOfStrings(char ** patterns, int patternsSize, char * word){
int count=0;
int lenw=strlen(word);
for(int i=0;i<patternsSize;i++){
if(kmp_pattern_match(patterns[i],word,lenw)){
count++;
}
}
return count;
}
相关文章
- 《图解算法》系列学习(三)
- NSGA2 算法MATLAB完整代码 中文注释详解
- OHEM算法及Caffe代码详解
- 【说站】python蒙特卡洛算法的介绍
- 当面试官问我vue的 diff算法时,我会理直气壮地这么说
- 【视频】Copula算法原理和R语言股市收益率相依性可视化分析|附代码数据
- word2vec中文词向量结合PCA算法在二维空间下可视化分析-代码
- 算法刷题-O(1) 时间插入、删除和获取随机元素、汇总区间
- C语言 | 动图演示十大经典排序算法(含代码)
- 【算法】动态规划 ① ( 动态规划简介 | 自底向上的动态规划示例 | 自顶向下的动态规划示例 )
- 蚁群算法应用到监控软件中之后都有什么作用
- 复杂网络社区发现算法聚类分析全国电梯故障数据和可视化:诊断电梯“安全之殇”|附代码数据
- Python用机器学习算法进行因果推断与增量、增益模型Uplift Modeling智能营销模型|附代码数据
- Boyer-Moore算法java实现详解编程语言
- Linux哈希算法:安全、可靠的认证方式(linuxhash算法)
- PHP各种排序算法实现代码
- PHP递归算法的详细示例分析
- C#中实现任意List的全组合算法代码
- 哈夫曼算法构造代码
- Dijkstra最短路径算法实现代码
- java数据结构和算法学习之汉诺塔示例
- 全排列算法的原理和实现代码