题目
题目来源leetcode
leetcode地址：28. 实现 strStr()，难度：简单。
题目描述(摘自leetcode)：
实现 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 仅由小写英文字符组成
本地调试代码：
class Solution { public int search(int[] nums, int target) { .... } public static void main(String[] args) { Solution solution = new Solution(); int[] arr = new int[]{-1,0,3,5,9,12};//这里修改数组内容 System.out.println(solution.search(arr, 2));//数组、目标值 } }
题解
NO1：暴力匹配法(超时)
思路：从前往后进行匹配，中间会使用一个临时节点来进行保存已经匹配的内容进行。
代码：
public int strStr(String haystack, String needle) { if (haystack == null || needle == null || "".equals(needle)) { return 0; } for (int i = 0; i < haystack.length(); i++) { int j = i; int k = 0; //临时保存中间与needle第一个字符相同的 int temp = -1;//若是下面没有匹配到就移动一格 while (k < needle.length() && j < haystack.length() && haystack.charAt(j) == needle.charAt(k)) { if (j > i && haystack.charAt(j) == needle.charAt(0) && temp == -1) { temp = j; } j++; k++; } if (k == needle.length()) { return i; } else if (temp != -1) { i = temp - 1; } } return -1; }
NO2：KMP算法
思路：若是查询的子串过长，不使用一些手段来过滤掉一些重复的操作就很容易超时。这里来使用KMP来获取前缀表并进行最长前后缀位置匹配，省略掉一些不需要重复进行比较的重复内容。
代码：时间复杂度O(m+n)
//构建前缀表 public void getNext(int[] next, String s) { if (next.length > 0) { int j = -1; next[0] = j; for (int i = 1; i < next.length; i++) { //j实际表示当前字符串是否带有前缀的标记，>0表示有，则将当前位置内容与原本前缀后一个元素是否相同，若是相同 while (j >= 0 && s.charAt(i) != s.charAt(j + 1)) { j = next[j]; } //用于进行更新当前前缀索引 if (s.charAt(i) == s.charAt(j + 1)) { j++; } next[i] = j; } } } public int strStr(String haystack, String needle) { if (haystack == null || needle == null || "".equals(needle)) { return 0; } int[] next = new int[needle.length()]; getNext(next, needle); //当前匹配的子串索引位置，之后比较都是需要索引位置+1进行判断 int j = -1; for (int i = 0; i < haystack.length(); i++) { //根据前缀表来匹配最近的重复前缀位置 while (j >= 0 && haystack.charAt(i) != needle.charAt(j + 1)) { j = next[j]; } //haystack与needle指定位置比较，若是相同加一，说明该子串匹配通过 if (haystack.charAt(i) == needle.charAt(j + 1)) { j++; } if (j == needle.length() - 1) { return (i - needle.length() + 1); } } return -1; }
