C++ KMP 算法详解：高效字符串查找实现

所以前缀表为：[0, 1, 0, 1, 2, 0]

🎯 前缀表的作用：当匹配失败时，告诉我们模式串应该跳到哪个位置继续匹配。

三、next 数组：前缀表的两种实现方式

在 KMP 中，通常用 next 数组来存储前缀表。但有两种主流实现：

方式 1️⃣：前缀表不减一（直接使用）

• next[i] = s[0..i] 的最长相等前后缀长度
• 示例："aabaaf" → next = [0, 1, 0, 1, 2, 0]

方式 2️⃣：前缀表统一减一（右移一位）

• next[0] = -1，其余 next[i] = 原前缀表 [i-1]
• 示例："aabaaf" → next = [-1, 0, -1, 0, 1, -1]

💡 两种方式都能正确工作，只是匹配时的指针逻辑不同。 本文将分别讲解两种实现！

四、方式一：前缀表不减一（推荐初学者）

步骤 1：构建 next 数组

void getNext(int* next, const string& s) {
    int j = 0; // j 表示前缀末尾
    next[0] = 0;
    for (int i = 1; i < s.size(); i++) {
        // 前后缀不相同，j 回退
        while (j > 0 && s[i] != s[j]) {
            j = next[j - 1];
        }
        // 前后缀相同，j 向前移动
        if (s[i] == s[j]) {
            j++;
        }
        next[i] = j; // 记录当前最长相等前后缀长度
    }
}

步骤 2：使用 next 数组匹配

int strStr(string haystack, string needle) {
    if (needle.empty()) return 0;
    vector<int> next(needle.size());
    getNext(next.data(), needle);
    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 - j + 1;
        }
    }
    return -1;
}