PALE13

28. 找出字符串中第一个匹配项的下标 - 力扣（LeetCode）

给你两个字符串 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 仅由小写英文字符组成

双指针

class Solution {
    public int strStr(String haystack, String needle) {
        int left = 0;
        int right = 0;
        int i = 0;
        while(right < haystack.length()){
            if(haystack.charAt(right) == needle.charAt(i)){
                right ++;
                i ++;
                if(i == needle.length()){
                    return left;
                }
            }else{
                left ++;
                right = left;
                i = 0;
            }
        }
        return -1;
    }

  
}

时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为 O(m*n)。

KMP算法

使用next数组记录最长相同的前后缀

next[i]表示下标i之前（包括i）的字符串中，有多大长度的相同前缀后缀。

前缀是指不包含最后一个字符的所有以第一个字符开头的连续子串。

后缀是指不包含第一个字符的所有以最后一个字符结尾的连续子串。

以字符串aabaaf为例

next数组为{0，1，0，1，2，0}

当模式串不匹配时，例如匹配到f匹配不成功，只需要找到f前面的字符串的最长相同前后缀，”aabaa”的最长相同前后缀为

2，即next[4] = 2，此时只需要用b和主串比较即可。因为f之前的”aabaa”都与主串匹配，而“aa”是最长的相同前后缀，不需要再进行重复的比较。

构造next数组

构造next数组的过程与匹配的过程相似

next[0] = 0，因为长度为1的串不存在最长相同前后缀

用 i 表示最长相同前后缀的长度，同时 i 也表示最长相同前缀尾部的下一个下标

j表示最长相同后缀尾部的下一个下标

即 i 从0开始遍历，j 从1开始遍历

如果s[ i ] == s[ j ] ，则 i++ ,表示最长相同前缀+1

否则 i = next[ i-1 ]， i 回退到上一次匹配的位置，相当于将 i 指针看作模式串

class Solution {
    public int strStr(String text, String needle) {
        int[] next =  getNext(needle); //生成needle的next数组

        int j = 0;
        for(int i = 0; i < text.length(); i++){
            while(j > 0 && text.charAt(i) != needle.charAt(j)){
                j = next[j-1]; //j回退到j-1的最长相同前缀的长度，也就是下一个需要比较的位置
            }
            if(text.charAt(i) == needle.charAt(j)){
                j++;
            }
            if(j == needle.length()){
                return i - needle.length() + 1;
            }
        }
        return -1;
    }

    public int[] getNext(String s){
        int[] next = new int[s.length()];
        int i = 0; //i为最长相同前后缀的长度,同时指向最长相同前缀的尾部的下标+1
        int j = 1; //j遍历next数组
        next[0] = i;
        while(j < s.length()){
            if(i > 0 && s.charAt(i) != s.charAt(j)){
                i = next[i-1]; //i回退到i-1的最长相同前缀，也就是[0,i]和[1,j]下一个需要比较的位置为next[i-1]
            }
            if(s.charAt(i) == s.charAt(j)){
                i++;//最长相同前后缀长度+1
            }
            next[j] = i; //以下标i为结尾的字符串的最长相同前后缀为j
            j++;
		} 
        return next;
    }
}

• 时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为 O(m+n)。