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

class Solution {
public:
    vector<int> getNext(const string s) {
        vector<int> next(s.size());
        next[0] = -1;
        int i = 0, j = -1;
        while (i < s.size() - 1) {
            if (j == -1 || s[j] == s[i]) {
                j++;
                i++;
                next[i] = j;
            } else {
                j = next[j];
            }
        }
        return next;
    }

    int strStr(string haystack, string needle) {
        vector<int> next = getNext(needle);
        int i = 0, j = 0;
        while (i < haystack.size()) {
            if (j == -1 || haystack[i] == needle[j]) {
                i++;
                j++;
                if (j == needle.size()) {
                    return i - j;
                }
            } else {
                j = next[j];
            }
        }
        return -1;
    }
};

这段代码实现了经典的字符串匹配算法 KMP。KMP 算法的核心是利用已经匹配的信息来避免重复匹配，从而提高匹配效率。

首先，我们来看 getNext 函数。该函数用于计算 needle 字符串的前缀表（prefix table），也称为失配函数（failure function）。前缀表是一个数组，其中第 i 个元素表示 needle 字符串中以第 i 个字符结尾的子串的最长前缀和最长后缀相等的长度。

具体来说，我们定义两个指针 i 和 j，其中 i 表示当前子串的结尾位置，j 表示当前子串的最长前缀和最长后缀相等的长度。初始化时，i 和 j 都指向字符串的开头，前缀表的第一个元素设为 -1。

接下来，我们在一个循环中不断计算前缀表中的元素。每次循环，我们比较 s[i] 和 s[j] 是否相等，如果相等，说明可以将 j 增加 1，同时将前缀表中下一个元素设为 j。如果不相等，我们需要将 j 回溯到前缀表中 j 对应的值，这是因为我们已经知道前面的 j 个字符是匹配的，所以可以直接跳过这些字符，从前面已经匹配的位置重新开始匹配。这个过程可以用递推式 j = next[j] 来描述。

最后，我们返回前缀表。

我们来看 strStr 函数。该函数用于在 haystack 字符串中查找 needle 字符串的第一个匹配项。首先，我们调用 getNext 函数计算出 needle 字符串的前缀表。然后，我们定义两个指针 i 和 j，其中 i 表示当前在 haystack 中匹配的位置，j 表示当前在 needle 中匹配的位置。初始化时，i 和 j 都指向字符串的开头。

我们在一个循环中不断尝试匹配 haystack 和 needle 中的字符。如果当前字符匹配成功，我们将 i 和 j 同时向后移动一个位置，继续匹配下一个字符。如果 j 到达了 needle 的末尾，说明已经找到了匹配项，我们可以返回 i - j。如果当前字符匹配失败，我们需要将 j 回溯到前缀表中 j 对应的值，重新开始匹配。这个过程可以用递推式 j = next[j] 来描述。如果 j 已经回溯到了 -1，说明在当前位置找不到匹配项，需要将 i 向后移动一个位置，重新开始匹配。

最后，如果循环结束还没有找到匹配项，说明在 haystack 中找不到 needle，需要返回 -1。

总体来说，这段代码的时间复杂度为 \(O(m+n)\)，其中 \(m\) 和 \(n\) 分别是 haystack 和 needle 的长度。这是因为在计算前缀表和匹配字符串时，指针 i 和 j 各自最多向前移动 \(m\) 和 \(n\) 次。空间复杂度为 \(O(n)\)，其中 \(n\) 是 needle 的长度，这是因为前缀表需要保存 needle 中每个位置的最长前缀和最长后缀相等的长度。

总之，这段代码非常经典和实用，可以在很多场景下使用，比如搜索引擎中的字符串匹配、文本编辑器中的搜索功能等等。