KMP算法

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

实现 strStr() 函数。

给定一个 haystack 字符串和一个 needle 字符串，在 haystack 字符串中找出 needle 字符串出现的第一个位置 (从0开始)。如果不存在，则返回  -1。

示例 1: 输入: haystack = “hello”, needle = “ll” 输出: 2

示例 2: 输入: haystack = “aaaaa”, needle = “bba” 输出: -1

说明: 当 needle 是空字符串时，我们应当返回什么值呢？这是一个在面试中很好的问题。 对于本题而言，当 needle 是空字符串时我们应当返回 0 。这与C语言的 strstr() 以及 Java的 indexOf() 定义相符。

---

我们称haystack为文本串，needle为模式串，长度分别为$m,n$
暴力算法很显然，但实在是太慢了，时间复杂度$O(mn)$

引入概念 “最长相等前后缀”.当长度为$n$字符串的前i个字符与后$i$个字符一样时，取最大的$i$称为最长相等前后缀长度，显然$i$不被允许是$n$。

这个概念有什么意义？当我们在检索文本串时，在不同字符之前的部分是完全相同的，也就是模式串的某一前缀，我们是已知他的组成的，如果我们知道这一前缀的最长相同前后缀长度，我们就可以在文本串上取后缀，模式串上取前缀，从而省去了不必要的计算，同时不需要前移文本串上的指针。

且由于模式串已知，我们在检索前可提前制出模式串所有前缀的最长相同前后缀长度，命为$next$数组(即模式串指针下一次的位置)。

先编写主程序部分，准备好预备数据后，在文本串上和模式串上置$i,j$指针，其中$i$只右移，我们可以以一个for循环做主循环:对每一个$i$，如果$i,j$处字符相同，则右移$j$一位，同时检测若$j$已超出模式串时，就可返回结果;若不同，则将j置于$next[j-1]$处，直至二者相同，或$j$已归$0$。这部分的时间复杂度是$O(m)$的，$j$指针右移必带动i指针右移，而i右移最多$j-1$次。

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

再看$next$数组的制备。暴力算法的时间复杂度是$O(n^2)$。这里再次用双指针，与主程序一样地，两个指针$i,j$分别指向后缀与前缀的末端。类似地，这部分的时间复杂度为$O(n)$
两个细节:

• 上一次$j$的截止蕴含了$next[i]$没有为$j+1$的可能
• $j$的左移调用$next[j]$以优化

vector<int> getNext(string s) {
    int len = s.size();
    vector<int> next(len);
    int j = 0;
    next[0] = 0;
    for (int i = 1; i < len; i++) {
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j;
    }
    return next;
}

剩下一些剪枝

if (n == 0) return 0;
if (m < n) return -1;
if (m == n) {
    for (int i = 0; i < m; i++) {
        if (haystack[i] != needle[i]) return -1;
    }
	return 0;
}

合并
总的时间复杂度为$O(m+n)$

class Solution {
public:
    vector<int> getNext(string s) {
        int len = s.size();
        vector<int> next(len);
        int j = 0;
        next[0] = 0;
        for (int i = 1; i < len; i++) {
            while (j > 0 && s[i] != s[j]) {
                j = next[j - 1];
            }
            if (s[i] == s[j]) {
                j++;
            }
            next[i] = j;
        }
        return next;
    }
    int strStr(string haystack, string needle) {
        int m = haystack.size(), n = needle.size();
        if (n == 0) return 0;
        if (m < n) return -1;
        if (m == n) {
            for (int i = 0; i < m; i++) {
                if (haystack[i] != needle[i]) return -1;
            }
            return 0;
        }
        int j = 0;
        vector<int> next = getNext(needle);
        for (int i = 0; i < m; i++) {
            while (j > 0 && haystack[i] != needle[j]) {
                j = next[j - 1];
            }
            if (haystack[i] == needle[j]) j++;
            if (j == n) return i - n + 1;
        }
        return -1;
    }
};