字符串-----7.KMP算法获取子串下标
2021/10/1 17:12:46
本文主要是介绍字符串-----7.KMP算法获取子串下标,对大家解决编程问题具有一定的参考价值,需要的程序猿们随着小编来一起学习吧!
第11日:实现 strStr()获取子串下标位置
题目链接:https://leetcode-cn.com/leetbook/read/top-interview-questions-easy/xnr003/
题目:
实现strStr()
函数。
给你两个字符串 haystack
和 needle
,请你在 haystack
字符串中找出 needle
字符串出现的第一个位置(下标从 0 开始)。如果不存在则返回-1
。
说明:
当 needle 是空字符串时,我们应当返回什么值呢?这是一个在面试中很好的问题。
对于本题而言,当 needle 是空字符串时我们应当返回 0 。这与 C 语言的 strstr() 以及 Java 的 indexOf() 定义相符。
示例 1:
输入:haystack = “hello”, needle = “ll”
输出:2
示例 2:
输入:haystack = “aaaaa”, needle = “bba”
输出:-1
示例 3:
输入:haystack = “”, needle = “”
输出:0
提示:
0 <= haystack.length, needle.length <= 5 * 104
haystack 和 needle 仅由小写英文字符组成
相关标签 双指针、字符串、字符串匹配
解题:
-
KMP算法
大致思路:
- 根据所给子串求出next数组
- 设置双指针i、j,遍历父串,如果两字符相同指针同时后移动,如果不相同同则回退到对应next数组下标所指位置,若对应next值为
-1
,则j
不动i++
。
详细代码如下:
/** * KMP算法案例 * 实现 strStr()获取子串下标值 */ public int strStr(String haystack, String needle) { if (needle.length() == 0) return 0; char[] parent = haystack.toCharArray();int i=0; char[] child = needle.toCharArray();int j=0; int[] next = getNext(needle); while (i<parent.length&&j<child.length){ if (parent[i]==child[j]){ i++; j++; }else { if (next[j]==-1) i++; else j=next[j]; } } if (j==next.length) return i-j; else return -1; } public static int[] getNext(String ps) { char[] chars = ps.toCharArray(); int[] next =new int[chars.length]; next[0]=-1; int i=0;//遍历字符数组的下标位置 int k=-1;//用来记录上一次next值,并可回溯之前的next() while (i<chars.length-1){ if (k==-1||chars[i]==chars[k]){ next[++i]=++k; }else{ k=next[k]; } } return next; }
- 求next数组比较晦涩难懂,如果没有基础,可以推荐去看KMP算法之求next数组代码讲解,我也看过其他视频,但这个让我突然秒懂。
这篇关于字符串-----7.KMP算法获取子串下标的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!
- 2024-07-04TiDB 资源管控的对撞测试以及最佳实践架构
- 2024-07-03万字长文聊聊Web3的组成架构
- 2024-07-02springboot项目无法注册到nacos-icode9专业技术文章分享
- 2024-06-26结对编程到底难不难?答案在这里
- 2024-06-19《2023版Java工程师》课程升级公告
- 2024-06-15matplotlib作图不显示3D图,怎么办?
- 2024-06-1503-Loki 日志监控
- 2024-06-1504-让LLM理解知识 -Prompt
- 2024-06-05做软件测试需要懂代码吗?
- 2024-06-0514-ShardingSphere的分布式主键实现