KMP 算法详解：高效字符串匹配的利器

这段代码实现了 KMP 算法来在字符串 'haystack' 中查找子串 'needle' 的位置。下面对代码进行原理解释：

getNext 函数用于计算目标子串的 next 数组，next 数组保存了每个位置的最长公共前后缀的长度。
在 getNext 函数中，使用双指针 i 和 j 来遍历字符串 s。其中，i 表示当前字符的索引，j 表示当前最长公共前后缀的结束位置。
首先，初始化 next[0] = 0，表示字符串的第一个位置没有公共前后缀。从 i = 1 开始遍历字符串 s。
在每次比较时，如果当前字符与前一个字符不匹配，则需要回溯到上一个最长公共前后缀的结束位置。这里使用 while 循环来实现回溯，直到找到匹配的字符或 j 为 0。
如果当前字符与前一个字符匹配，则 j++，继续下一个字符的比较。
最后，将最长公共前后缀的长度 j 保存到 next[i] 中。
在 kmp 函数中，首先判断目标子串 'needle' 是否为空，若为空，则直接返回 0。
创建长度为 'needle.size()' 的 next 数组，然后调用 getNext 函数计算目标子串 'needle' 的 next 数组。
使用双指针 i 和 j 遍历源字符串 'haystack'，其中 i 表示当前字符的索引，j 表示目标子串 'needle' 的索引。
当当前字符与目标子串中的字符不匹配时，需要回溯到上一个最长公共前后缀的结束位置。同样使用 while 循环实现回溯，直到找到匹配的字符或 j 为 0。
如果当前字符与目标子串中的字符匹配，则 j++，继续下一个字符的比较。
如果 j 的值等于目标子串的长度，说明完全匹配了目标子串，返回起始位置的索引 (i - 'needle.size()' + 1)。
如果遍历完整个源字符串 'haystack' 后仍然未找到目标子串，返回 -1。
在 main 函数中，创建 Solution 类的对象 solution，并给出源字符串 'haystack' 和目标子串 'needle'。
调用 solution 对象的 kmp 方法来查找目标子串的位置，并将结果存储在 result 变量中。
最后，输出 result，即目标子串的起始位置的索引。

这段代码通过 KMP 算法实现了高效的字符串匹配，避免了不必要的比较，提高了匹配效率。

#include <iostream>
using namespace std;

class Solution {
public:
    void getNext(int* next, const string& s) {
        int j = 0;
        next[0] = 0;  // 初始化 next 数组
        for (int i = 1; i < s.size(); i++) {  // 从 1 开始遍历字符串 s
            while (j > 0 && s[i] != s[j]) {  // 如果当前字符与前一个字符不匹配，则回溯到上一个最长公共前后缀的位置继续比较
                j = next[j - 1];  // 通过 next 数组回溯到上一个最长公共前后缀的结束位置
            }
            if (s[i] == s[j]) {  // 当前字符与前一个字符匹配
                j++;  // 继续下一个字符的比较
            }
            next[i] = j;  // 保存最长公共前后缀的长度
        }
    }
    int kmp(string haystack, string needle) {
        if (needle.size() == 0) {
            return 0;  // 目标子串为空，直接返回 0
        }
        int* next = new int[needle.size()];  // 创建 next 数组
        getNext(next, needle);  // 计算目标子串的 next 数组
        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]) {  // 当前字符与目标子串中的字符匹配
                j++;  // 继续下一个字符的比较
            }
            if (j == needle.size()) {  // 完全匹配目标子串
                return (i - needle.size() + 1);  // 返回起始位置的索引
            }
        }
        return -1;  // 源字符串中未找到目标子串
    }
};

int main() {
    Solution solution;
    string haystack = 'hello world';
    string needle = 'world';
    int result = solution.kmp(haystack, needle);
    cout << '匹配时下标为: ' << result << endl;
    return 0;
}