28. 找出字符串中第一个匹配项的下标

给你两个字符串 haystack 和 needle ，请你在 haystack 字符串中找出 needle 字符串的第一个匹配项的下标（下标从 0 开始）。如果 needle 不是 haystack 的一部分，则返回 -1 。

示例1

• 输入

  haystack = "sadbutsad", needle = "sad"

• 输出

  0

示例2

• 输入

  haystack = "leetcode", needle = "leeto"

• 输出

  -1

题解 KMP算法

算法的核心思想是利用字符串needle的前缀函数，来加速遍历给定字符串haystack的过程。该前缀函数next[i]的定义如下:对于给定的长度为m的字符串needle，next[i](0<=i<m)表示needle[0,i]子串中，真前缀与真后缀相等的最长长度。

下面是一个简单的例子,该字符串 “XXYXXYabc” 的子串 “XXYXXY”的前缀数为3，因为前缀XXY=后缀XXY，长度为3.

在拥有了这个前缀数组的帮助下，我们可以在进行字符串比较时进行加速，加速过程如下：如下图所示，当前匹配到下标index处，发现index处字符不相同，在常规暴力匹配方式下，发现字符匹配失败后，需要回到haystack[该次匹配起点+1]处继续检索。但在拥有前缀数组next的帮助下，我们并不需要改变在haystack中index的位置，首先由于先前的遍历，已知子串str1=str2，

且通过next，可以获取最长长度的相等的真前缀和真后缀，可以得到在needle的子串str2中，又有S3=S4，根据先前str1=str2，可以得到S1=S2=S3=S4。

所以 S2=S3 ，在不经意间已经完成了需要遍历匹配的S3的部分，那么我们完全没必要回退haystack中的index，只需要回退needle的index，到橙色部分的字符处，将其与当前字符进行比较，继续推进。这里回退到的位置，就是前缀/后缀的长度，也就是next中对应的值。

我们保证了已经遍历过了S3部分，但我们又是如何保证，匹配的起点不会在S1~S2之间出现的呢？下面给出证明过程。反证法：假设S1~S2间有个k位置是正确答案。

那说明haystack中k位置开始到当前位置整段，即紫色部分，与needle中紫色部分相同。

又因为先前的遍历确保了上下完全对映相等，又有下面的2处紫色部分相等。

结果很明显了，这会导致needle中出现紫色前缀和紫色后缀相等，且其长度比next中给定的前后缀长度更长，这显然违背了next中“长度最长”的定义，出现矛盾，说明k位置并不存在，论证完毕。

在这种加速下，haystack的index永远不会回退，只会前进，而每一轮匹配仅有比较和查询next数组的操作，复杂度O(1)，我们仅需遍历2个字符串，故时间复杂度为:

$$ O(m+n) $$

如何求前缀函数next,下面给出手写过程及证明：

---

代码

class Solution {
    public int strStr(String haystack, String needle) {
        // n、m字符串长度
        int n = haystack.length(), m = needle.length();
        //边界情况
        if (m == 0) {
            return 0;
        }
        //求解next数组
        int[] next = new int[m];
        for (int i = 1, j = 0; i < m; i++) {
            while (j > 0 && needle.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (needle.charAt(i) == needle.charAt(j)) {
                j++;
            }
            next[i] = j;
        }
        //KMP
        for (int i = 0, j = 0; i < n; i++) {
            while (j > 0 && haystack.charAt(i) != needle.charAt(j)) {
                j = next[j - 1];
            }
            if (haystack.charAt(i) == needle.charAt(j)) {
                j++;
            }
            if (j == m) {
                return i - m + 1;
            }
        }
        return -1;
    }
}

复杂度分析

• 时间复杂度:
  $$ O(m+n) $$
• 空间复杂度
  $$ O(m) $$