LeetCode--28.找出字符串中第一个匹配项的下标（字符串/KMP算法）

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仅由小写英文字符组成

解题思路

利用KMP算法：

其核心步骤为：

1、根据模式串T，求出next数组

2、利用next数组进行匹配（主字符串指针不回溯）

求next数组步骤：

代码

classSolution{publicvoidgetNext(Strings,int[]next){// 初始化intj=-1;next[0]=j;for(inti=1;i<s.length();i++){// 最长前缀和最长后缀不匹配// 这里只关注第i个字符左侧字符串（不包含i）的前后缀while(j>=0&&s.charAt(i-1)!=s.charAt(j)){// 回退j=next[j];}// 匹配成功（默认j=-1为通配符，均匹配成功）j++;next[i]=j;}}publicintstrStr(Stringhaystack,Stringneedle){// 初始化next数组int[]next=newint[needle.length()];getNext(needle,next);// 初始化i,jinti=0;intj=0;while(i<haystack.length()&&j<needle.length()){if(haystack.charAt(i)==needle.charAt(j)){i++;j++;}else{// 若不匹配，i不变，通过next[j]找已匹配的子串while(j>=0&&haystack.charAt(i)!=needle.charAt(j)){// 回退j=next[j];}i++;j++;}}if(j==needle.length())returni-j;return-1;}}