Leetcode刷题（二十八）

找出字符串中第一个匹配项的下标（Easy）

给你两个字符串 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 仅由小写英文字符组成
Related Topics
双指针
字符串
字符串匹配

思路分析

这道题是很经典的字符串匹配算法，这里第一个想到的就是KMP字符串匹配算法，这是很经典的数据结构算法，直接使用该算法就可以完成这道题。

这里我来复习一下什么是KMP算法：
首先我们要知道朴素字符串匹配会导致指针不断进行回溯，导致浪费。而KMP算法中的目标指针并不回溯，而是模式串的指针根据得到的next[]数组来进行部分回溯，并且不会重复比对一定相同的字符串。这样就节省了很多时间。比如说目标串为：ABCABEABCABCMN，模式串为：ABCABCMN。由这个例子可以看出，如果是朴素匹配，那么在对比到第一个E出现之后指针就有进行回溯，回溯到目标串[1]的位置，

但是如果使用kmp算法，那么目标串的指针并不需要回溯，只需要根据next矩阵来回溯模式串的指针，这里需要回溯到模式串[2]的位置，以此类推。

KMP算法的核心就是如何计算模式串的next[]数组，要想理解如何计算该数组，首先要了解最长相同前后缀的概念。举一个例子就可以明白了，模式串ABCXABCMN，这里对于M位置的前缀：ABC，后缀：ABC.这里要注意，你想找某个位置的最长相同前后缀，那么后缀就不能包括这个位置，比如上面的例子就不包括M。那么这里我们同时也要说一下next数组中元素的含义就是回溯的位置，next[j] = i 的意思就是位置j的元素回溯到位置i。这里我们来看一下求next的公式。

公式通俗的解释就是1.当存在相同前后缀的时候，next[i]的值表示下标为i的字符前的字符串最长相等前后缀的长度。2. j = 0 的时候，也就是字符串第一个元素的时候，初始化为 -1。 3.其他没有相同前后缀的情况，设置为 0 .

同时要了解KMP算法还存在弊端，还可以继续优化，但这里就不再赘述，网上有很多讲解，这里主要还是刷题。

代码实现

//leetcode submit region begin(Prohibit modification and deletion)
class Solution {
    public int strStr(String haystack, String needle) {
        int flag = -1;
        int j = 0;
        int i = 0;
        int[] next = builtNext(needle);
        while (i < haystack.length() && j < needle.length()){
            if (j == -1 || haystack.charAt(i) == needle.charAt(j)){
                j++;
                i++;
            }else {
                j = next[j];
            }
            if (j == needle.length()) flag = i-j;//返回匹配开始的位置
        }

        return flag;
    }
//计算NEXT数组
    public int[] builtNext(String needle){
        int j = 0;
        int k = -1;
        int[] next = new int[needle.length()];
        next[0] = -1;
        while (j < needle.length()-1){
            if (k == -1 || needle.charAt(k) == needle.charAt(j)){
                k++;
                j++;
                next[j] = k;
            }else {
                k = next[k];
            }
        }

        return next;
    }
}
//leetcode submit region end(Prohibit modification and deletion)