kmp算法 LeetCode

KMP算法（Knuth-Morris-Pratt算法）是一种字符串匹配算法，用于在一个文本串S内查找一个模式串P的出现位置。它的核心思想是利用已经匹配过的部分字符，避免不必要的回溯。

在LeetCode上，有一些问题可以用KMP算法解决。例如，LeetCode第28题 "Implement strStr()" 就可以用KMP算法来实现。这道题的要求是在一个字符串haystack中找到另一个字符串needle的第一次出现位置。

以下是使用KMP算法解决这道题的大致思路：
1. 构建模式串needle的最长前缀后缀数组next[]。next[i]表示模式串needle中以i结尾的子串的最长相同前缀后缀长度。
2. 在文本串haystack中使用模式串needle进行匹配，比较haystack[i]与needle[j]是否相等：
- 若相等，则i和j同时向后移动一位；
- 若不相等，则根据next[j]的值，更新j的位置。

具体实现可以参考以下代码：

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