27-算法打卡-字符串-找出字符串中第一个匹配项的下标-leetcode(28)-第二十七天
1 题目地址
28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）28. 找出字符串中第一个匹配项的下标 - 给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。 示例 1：输入：haystack = "sadbutsad", needle = "sad"输出：0解释："sad" 在下标 0 和 6 处匹配。第一个匹配项的下标是 0 ，所以返回 0 。示例 2：输入：haystack = "leetcode", needle = "leeto"输出：-1解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。 提示： * 1 <= haystack.length, needle.length <= 104 * haystack 和 needle 仅由小写英文字符组成
https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string/description/
2 题目说明
给你两个字符串
haystack和needle，请你在haystack字符串中找出needle字符串的第一个匹配项的下标（下标从 0 开始）。如果needle不是haystack的一部分，则返回-1。示例 1：
输入：haystack = "sadbutsad", needle = "sad" 输出：0 解释："sad" 在下标 0 和 6 处匹配。 第一个匹配项的下标是 0 ，所以返回 0 。示例 2：
输入：haystack = "leetcode", needle = "leeto" 输出：-1 解释："leeto" 没有在 "leetcode" 中出现，所以返回 -1 。提示：
1 <= haystack.length, needle.length <= 104haystack和needle仅由小写英文字符组成
3 解题思路
方式一：暴力方式：两层循环
1、假设字符串haystack长度是m，needle长度是n
2、haystack匹配needle最多需要循环次数是m-n+1
3、第一层循环是最多需要遍历的次数m-n+1，即haystack的起始的索引下标位置
4、第二层循环每次都是从0开始最大到needle长度n，判断两层的指向的字符是否相等，
不相等：直接跳出第二层循环
相等：第二层是否遍历到needle的末尾
是：直接返回第一层索引下标(结果)
否：上下两层同时向后移动
方式二：KMP
查看 28-算法打卡-字符串-KMP算法理论-第二十八天-CSDN博客、29-算法打卡-字符串-KMP算法理论2-第二十九天-CSDN博客
核心思想是记录已经遍历过的模式串的特征，当匹配失败的时候只需要模式串退回，文本串继续向右移动，减少时间复杂度O(m+n)。
获取前缀表(next数组)：
1、初始化：初始化指针i j， j指向前缀的末尾也是子串的最长公共前后缀、i指向后缀的
末尾也是待更新next数组的位置； j=0,next[0]=0
2、前后缀相同： j向右移动，next[i]=j
3、前后缀不相同：j回退到next[j-1]位置 ，不相等一直回退，即是while，而不是if4、更新next数组，next[i]=j
获取匹配下标：
1、获取next数组
2、定义指针i j，i指向
haystack开始位置(0), j指向needle开始位置(0)3、文本串和模式串指向的位置相同时：则两者都继续向右移动
4、文本串和模式串指向的位置不相同时：模式串退回到next[j-1]的位置
4 代码编写
4.1 暴力方式
class Solution {public int strStr(String haystack, String needle) {char[] haystackArray = haystack.toCharArray();char[] needleArray = needle.toCharArray();int haystackLength = haystackArray.length;int needleLength = needleArray.length;// 需要匹配的次数int need = haystackLength - needleLength + 1;for (int i=0; i<need; i++) {int left = i;int needleInit = 0;while (needleInit<needleLength) {// 字符相等if (haystackArray[left] == needleArray[needleInit]) {// 最后一个元素也匹配直接返回if (needleInit == needleLength-1) {return i;}// 否则都向后移动left++;needleInit++;} else {// 不相等，直接跳出本层循环break;}}}return -1;}}
简化上面代码方式：
class Solution {public int strStr(String haystack, String needle) {char[] haystackArray = haystack.toCharArray();char[] needleArray = needle.toCharArray();int haystackLength = haystackArray.length;int needleLength = needleArray.length;// 需要匹配的次数int need = haystackLength - needleLength + 1;for (int i=0; i<need; i++) {int left = i;int needleInit = 0;// 匹配则向后移动while (needleInit<needleLength && haystackArray[left] == needleArray[needleInit]) {left++;needleInit++;}// 最后一个元素也匹配直接返回if (needleInit == needleLength) {return i;}}return -1;}}
4.2 KMP
class Solution {public int strStr(String haystack, String needle) {int m = haystack.length();int n = needle.length();int[] next = new int[n];getNext(needle, next);int j = 0;for (int i=0; i<m; i++) {while (j>0 && haystack.charAt(i) != needle.charAt(j)) {j = next[j-1];}if (haystack.charAt(i) == needle.charAt(j)) {j++;}if (j==n) {return (i-j+1);}}return -1;}// 获取前缀表public void getNext(String needle, int[] next) {// 初始化，j后缀的末尾，子串的最长公共前后缀int j = 0;next[0] = 0;// i前缀的末尾，数组next更新索引位置for (int i=1; i<needle.length(); i++) {while (j>0 && needle.charAt(i)!= needle.charAt(j)) {// 向左回退j = next[j-1];}// 匹配成功向右移动if (needle.charAt(i)== needle.charAt(j)) {j++;}// 更新数组next[i] = j;}}}