扬州网站建设 开元百度访问量统计

一、题目描述

给你两个字符串 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 。

来源：力扣（LeetCode）

链接：https://leetcode.cn/problems/find-the-index-of-the-first-occurrence-in-a-string

著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

二、运行结果

暴力匹配运行结果：

KMP算法运行结果：

三、解题思路

一、暴力匹配：两层循环

二、KMP匹配算法：首先计算匹配串的next数组，然后遍历源串和匹配串进行匹配，当不匹配时，根据next数组进行跳转，源串的指针不用回溯，时间效率更高。

四、AC代码

一、暴力匹配代码

class Solution {public int strStr(String haystack, String needle) {int len1 = haystack.length();int len2 = needle.length();for(int i=0; i<=len1-len2; ++i){for(int j=0; j<len2; ++j){if(j == (len2-1) && needle.charAt(j) == haystack.charAt(i+j))return i;if(needle.charAt(j) != haystack.charAt(i+j))break;}}return -1;}
}

二、KMP算法匹配代码

class Solution {public int strStr(String haystack, String needle) {// KMP匹配算法int len1 = haystack.length();int len2 = needle.length();if(len2 == 0) return 0;//转换为字符数组方便操作char[] hArr = haystack.toCharArray(); char[] nArr = needle.toCharArray(); // 构建next数组(next数组和匹配串相关)int[] next = new int[len2];for(int i=1, j=0; i<len2; i++){while(j > 0 && nArr[i] != nArr[j]) j = next[j-1]; if(nArr[i] == nArr[j]) j++;next[i] = j;}//利用next指针进行跳转，源串的指针不用回溯for(int i=0, j=0; i<len1; i++){while(j > 0 && hArr[i] != nArr[j]) j = next[j-1];if(hArr[i] == nArr[j]) j++;if(j == len2) //匹配串已经在源串中完全找到return i-j+1;}return -1;}
}