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

题目：

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

思路：

KMP解法
KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。

采用暴力解法，不考虑剪枝的话复杂度是 O(m∗n) 的，而 KMP 算法的复杂度为 O(m+n)。

KMP 之所以能够在 O(m+n) 复杂度内完成查找，是因为其能在「非完全匹配」的过程中提取到有效信息进行复用，以减少「重复匹配」的消耗。

​ KMP算法的核心在next数组，如果能够理解next数组的求解过程，就会发现子串和主串的匹配过程，是和求next数组的过程是完全一致的。

先不考虑KMP算法中next数组的作用，先从简单的概念入手。抛开KMP算法而言，next数组是有它本身的含义的：就是字符串的最长公共（相等）前后缀的大小。

​ 我们从最长公共（相等）前后缀的大小这个定义出发，来求解next数组，并逐渐理解KMP算法的核心思想。

1. 最长公共（相等）前后缀
   在模拟 KMP 匹配过程之前，我们先建立两个重要概念：
   • 前缀：是指不包含最后一个字符，然后所有以第一个字符开头的连续子串。
   • 后缀：是指不包含第一个字符，然后所有以最后一个字符结尾的连续子串。

例：对于字符串"abcab"，它有"a" “ab” “abc” “abca” 这样四个前缀。

同样，对于字符串"abcab"，它有"b" “ab” “cab” “bcab” 这样四个后缀。

然后我们假设原串为 abeababeabf，匹配串为 abeabf：

• 最长公共（相等）前后缀（的长度）

最长公共前后缀的定义是：按照前后缀的长度，从小到大比较，从各组相等的前后缀中，返回长度最大的一组前后缀的长度。

如果字符串中不存在任一组前后缀相等，那么该字符串最长公共前后缀的长度就是 0。（公共：指的就是前后缀相等。）

举例说明：

对于字符串"abcab"，求最长公共前后缀长度的过程如下：

特殊情况：对于空字符串或只包含一个字符的字符串，其最长公共前后缀的长度为0。

2. 匹配过程

   我们假设原串为 abeababeabf，匹配串为 abeabf：
   

• 暴力解法：

  首先在「原串」和「匹配串」分别各自有一个指针指向当前匹配的位置。

  首次匹配的「发起点」是第一个字符 a。显然，后面的 abeab 都是匹配的，两个指针会同时往右移动（黑标）。

  在都能匹配上 abeab 的部分，「暴力解法」和「KMP」并无不同。

  直到出现第一个不同的位置（红标）：
  
  接下来，正是「暴力解法」和「KMP」出现不同的地方：

  先看下「暴力解法」逻辑：

  1. 将原串的指针移动至本次「发起点」的下一个位置（b 字符处）；匹配串的指针移动至起始位置。

  2. 尝试匹配，发现对不上，原串的指针会一直往后移动，直到能够与匹配串对上位置。

  如图：
  
  也就是说，对于「暴力解法」而言，一旦匹配失败，将会将原串指针调整至下一个「发起点」，匹配串的指针调整至起始位置，然后重新尝试匹配。

  这也就不难理解为什么「暴力解法」的复杂度是 O(m∗n) 了。

• 然后我们再看看「KMP 匹配」过程：

  首先匹配串会检查之前已经匹配成功的部分中里是否存在相同的「前缀」和「后缀」。如果存在，则跳转到「前缀」的下一个位置继续往下匹配：
  
  跳转到下一匹配位置后，尝试匹配，发现两个指针的字符对不上，并且此时匹配串指针前面不存在相同的「前缀」和「后缀」，这时候只能回到匹配串的起始位置重新开始：
  
  到这里，你应该清楚 KMP 为什么相比于暴力解法更快：

  • 因为 KMP 利用已匹配部分中相同的「前缀」和「后缀」来加速下一次的匹配。
  • 因为 KMP 的原串指针不会进行回溯（没有暴力解法中回到下一个「发起点」的过程）。

  如果严格按照上述解法的话，最坏情况下我们需要扫描整个原串，复杂度为 O(n)。同时在每一次匹配失败时，去检查已匹配部分的相同「前缀」和「后缀」，跳转到「前缀」的下一位置继续匹配，如果不匹配则再检查前面部分是否还有有相同「前缀」和「后缀」，再跳转到「前缀」的下一位置继续匹配 … 这部分的复杂度是 O($m^2$ ) ，因此整体的复杂度是 O($n\ast m^2$)，而我们的暴力解法是 O(m∗n) 的。

  说明还有一些性质我们没有利用到。

  显然，扫描完整原串操作这一操作是不可避免的，我们可以优化的只能是「检查已匹配部分的相同前缀和后缀」这一过程。我们检查「前缀」和「后缀」的目的其实是「为了确定匹配串中的下一段开始匹配的位置」。

  同时我们发现，对于匹配串的任意一个位置而言，由该位置发起的下一个匹配点位置其实与原串无关。

  举个 🌰，对于匹配串 abcabd 的字符 d 而言，由它发起的下一个匹配点跳转必然是字符 c 的位置。因为字符 d 位置的相同「前缀」和「后缀」字符 ab 的下一位置就是字符 c。

  可见从匹配串某个位置跳转下一个匹配位置这一过程是与原串无关的，我们将这一过程称为找 next 点。

  显然我们可以预处理出 next 数组，数组中每个位置的值就是该下标应该跳转的目标位置（ next 点），并且要在 O(m) 的复杂度内预处理出 next数组。

  当我们进行了这一步优化之后，复杂度整个 KMP 过程是 O(m+n) 。

3. next 数组的构建

   接下来，我们看看 next 数组是如何在 O(m) 的复杂度内被预处理出来的。

   假设有匹配串 aaabbab，我们来看看对应的 next 是如何被构建出来的。
   
   
   
   
   这就是整个 next 数组的构建过程，时空复杂度均为 O(m)。

   至此整个 KMP 匹配过程复杂度是 O(m+n) 的。

   其实netx数组也就是匹配串的一个前缀表，匹配串的前缀表：记录下标i之前（包括i）的匹配串中，最长公共（相等）前后缀的长度。

   • aaabbab的前一个字符为a，最长公共（相等）前后缀的长度为0。
   • aaabbab的前两个字符为aa，最长公共（相等）前后缀的长度为1。
   • aaabbab的前三个字符为aaa，最长公共（相等）前后缀的长度为2。
   • 以此类推得到aaabbab的前缀表为[0,1,2,0,0,1,0]，所以next数组也为[0,1,2,0,0,1,0]。
     
     构建next数组的代码如下：

    void getNext(int* next, const string& p) {
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < p.size(); i++) {
            while (j > 0 && p[i] != p[j]) { // j要保证大于0，因为下面有取j-1作为数组下标的操作
                j = next[j - 1]; // 注意这里，是要找前一位的对应的回退位置了
            }
            if (p[i] == p[j]) {
                j++;
            }
            next[i] = j;
        }
    }

代码：

class Solution {
public:
    void getNext(int* next, const string& p){
        int j = 0;
        next[0] = 0;
        for(int i = 1; i < p.size(); i++){  // 注意i从1开始
            while(j > 0 && p[i] != p[j]){
                j = next[j - 1];    // 不相等了j指针指向前一位置的next数组对应的值
            }
            if(p[i] == p[j]){
                j++;    // 相等了i和j指针同时后移
            }
            next[i] = j;
        }
    }

    int strStr(string haystack, string needle) {
        if(needle.size() == 0){
            return 0;
        }
        vector<int> next(needle.size());
        getNext(&next[0], needle);
        // KMP匹配过程
        int j = 0;
        for(int i = 0; i < haystack.size(); i++){
            while(j > 0 && haystack[i] != needle[j]){   // 不匹配
                j = next[j - 1];    // 跳到之前匹配的位置
            }
            if(haystack[i] == needle[j]){   // 匹配，i和j同时后移
                j++;
            }
            if(j == needle.size()){ // 文本串haystack中出现了needle
                return (i - needle.size() + 1);
            }
        }
        return -1;
    }
};

总结：

时间复杂度：n 为原串的长度，m 为匹配串的长度。复杂度为 O(m+n)。
空间复杂度：构建了 next 数组。复杂度为 O(m)。

KMP 算法是一个快速查找匹配串的算法，它的作用其实就是本题问题：如何快速在「原字符串」中找到「匹配字符串」。

KMP匹配过程中，原串不用回溯到起始点，匹配串只需根据预处理得到的next数组回溯到上一匹配位置，再将该位置字符与原串中的当前字符进行匹配，反复进行上述过程就可以快速在「原字符串」中找到「匹配字符串」，避免了暴力解法中不配时，原串和匹配串要回溯到起点。

参考：

代码随想录
leetcode题解
leetcode题解