LeetCode-28 实现strStr() KMP算法的学习
2024-09-08 18:17:20
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/repeated-string-match
题目描述
给定两个字符串 a 和 b,寻找重复叠加字符串 a 的最小次数,使得字符串 b 成为叠加后的字符串 a 的子串,如果不存在则返回 -1。
注意:字符串 "abc" 重复叠加 0 次是 "",重复叠加 1 次是 "abc",重复叠加 2 次是 "abcabc"。
示例 1:
输入:a = "abcd", b = "cdabcdab"
输出:3
解释:a 重复叠加三遍后为 "abcdabcdabcd", 此时 b 是其子串。
示例 2:
输入:a = "a", b = "aa"
输出:2
示例 3:
输入:a = "a", b = "a"
输出:1
示例 4:
输入:a = "abc", b = "wxyz"
输出:-1
解题思路
对于这种问题,暴力法也叫朴素求解法是将两个字符串一个一个比较,可以肯定复杂度为O(mn),但是通过KMP算法,可以将复杂度下降到O(m+n).
KMP算法的原理是,在匹配过程中,匹配字符串之中会有重复的字符,遍历过后如果使用朴素算法,会有多次的遍历,可以使用一个next数组,将有相同前缀的标记起来,在遍历的时候便可以跳过遍历前缀的过程,大大提高了解题效率
next数组构建过程如下:(借用宫水三叶大佬的两张图)
这样,在两个字符串比较过程中,如果发现字符比较不相同,可以直接跳到与当前字符串有相同前缀的字符上,不需要从头开始进行计算。
代码展示
class Solution {
public:
int strStr(string haystack, string needle) {
int m = haystack.size();
int n = needle.size();
if(n == 0) return 0;
int iRet = 0;
vector<int> viNext(n, 0);
for(int i = 1, j = 0; i < n; i++)
{
while(needle[i] != needle[j] && j > 0)
{
j = viNext[j - 1];
}
if(needle[i] != needle[j])
{
viNext[i] = 0;
}
else
{
viNext[i] = j + 1;
j++;
}
}
for(int i = 0, j = 0; i < m; i++)
{
while(haystack[i] != needle[j] && j > 0)
{
j = viNext[j - 1];
}
if(haystack[i] != needle[j])
{
j = 0;
}
else
{
j++;
}
if(j == n)
{
return i - n + 1;
}
}
return -1;
}
};
运行结果
最新文章
- Nginx相关集合
- #1014 Trie树
- 用 Mahout 和 Elasticsearch 实现推荐系统
- Jenkins进阶系列之——04Publish Over FTP Plugin插件
- 如何区分 OpenStack Neutron Extension 和 Plugin
- leetcode 99 Recover Binary Search Tree ----- java
- Django视频教程 - 基于Python的Web框架(全13集)
- 【转载】Deep Learning(深度学习)学习笔记整理
- LA 4726 再看斜率优化
- EC读书笔记系列之19:条款49、50、51、52
- weblogic 集群部署时上传jsp不更新问题
- js 操作 cookie
- JVM高级特性-一、java内存结构区域介绍
- Handlebars.js 模板引擎
- 用于Spring Boot Jar部署的shell脚本
- Mathematica查看内部定义
- ArrayList 的代码
- Redis入门到高可用(二十一)——缓存的使用和设计
- 深入理解vue-router之keep-alive
- iOS - is missing from working copy