KMP 算法实现及多种 next 数组约定笔记

题目：字符串匹配问题

实现 KMP 算法，在文本字符串中查找模式字符串的首次出现位置。如果找到，返回起始索引；否则返回 -1。

样例输入和输出

• 文本字符串: "ABABDABACDABABCABAB"
• 模式字符串: "ABABCABAB"
• 输出: 匹配起始索引为 10（基于 0 的索引）

验证：文本中从索引 10 开始的子串 "ABABCABAB" 与模式匹配。

完整代码实现（使用 next[0] = -1 约定）

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

// 生成 next 数组，next[0] = -1
int* getNext(char* pattern) {
    int n = strlen(pattern);
    int* next = (int*)malloc(sizeof(int) * n);
    if (n == 0) return next;
    next[0] = -1;
    int i = 0, j = -1;
    while (i < n - 1) {
        if (j == -1 || pattern[i] == pattern[j]) {
            i++;
            j++;
            next[i] = j;
        } else {
            j = next[j];
        }
    }
    return next;
}

// KMP 搜索函数
int kmpSearch(char* text, char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    if (m == 0) return 0; // 空模式总是匹配
    int* next = getNext(pattern);
    int i = 0, j = 0;
    while (i < n && j < m) {
        if (j == -1 || text[i] == pattern[j]) {
            i++;
            j++;
        } else {
            j = next[j];
        }
    }
    free(next);
    if (j == m) {
        return i - j; // 返回匹配起始索引
    } else {
        return -1; // 未找到
    }
}

int main() {
    char text[] = "ABABDABACDABABCABAB";
    char pattern[] = "ABABCABAB";
    int pos = kmpSearch(text, pattern);
    if (pos != -1) {
        printf("Pattern found at index %d\n", pos);
    } else {
        printf("Pattern not found\n");
    }
    return 0;
}

多种 next 数组约定笔记

在 KMP 算法中，next 数组有不同的约定，主要影响初始值和跳转逻辑。以下是两种常见约定：

1. next[0] = -1 约定

• 含义: next[i] 表示当模式串的第 i 个字符（0-indexed）不匹配时，应跳转到模式串的 next[i] 位置继续匹配。如果 next[i] = -1，表示模式串的第一个字符都不匹配，此时模式串整体右移，文本指针前进。

• next 数组计算:

  • next[0] = -1
  • 使用双指针 i 和 j，其中 j 初始为 -1。
  • 算法逻辑：如果 j == -1 或当前字符匹配，则 i 和 j 递增，并设置 next[i] = j；否则，j 回退到 next[j]。

• 匹配过程:

  • 直接使用 j = next[j] 进行跳转，包括当 j == -1 时处理文本指针前进。

2. next[0] = 0 约定（前缀函数）

• 含义: next[i] 表示子串 pattern[0:i] 的最长公共前后缀的长度（不包括自身）。当不匹配时，跳转到 next[j-1] 的位置（如果 j>0），否则文本指针前进。

• next 数组计算:

  • next[0] = 0
  • 使用双指针 i 和 j，其中 j 初始为 0，i 初始为 1。
  • 算法逻辑：如果当前字符匹配，则 j 递增并设置 next[i] = j，然后 i 递增；否则，如果 j != 0，则 j 回退到 next[j-1]；如果 j == 0，则设置 next[i] = 0 并 i 递增。

• 匹配过程:

  • 需要判断 j 是否为零：如果不匹配且 j > 0，则 j = next[j-1]；如果 j == 0，则文本指针 i 前进。

等价性

两种约定在功能上是等价的，只是实现细节不同。第一种约定（next[0] = -1）在跳转时更直接，而第二种约定（next[0] = 0）更强调前缀函数的概念。

示例：模式 "ABABCABAB" 的 next 数组

• 使用 next[0] = -1 约定:
  next = [-1, 0, 0, 1, 2, 0, 1, 2, 3]
• 使用 next[0] = 0 约定:
  next = [0, 0, 1, 2, 0, 1, 2, 3, 4]（注意：这里的 next[i] 表示长度，因此值比第一种约定大 1）

第二种约定的代码示例

// 生成 next 数组，next[0] = 0
int* getNext2(char* pattern) {
    int n = strlen(pattern);
    int* next = (int*)malloc(sizeof(int) * n);
    if (n == 0) return next;
    next[0] = 0;
    int i = 1, j = 0;
    while (i < n) {
        if (pattern[i] == pattern[j]) {
            j++;
            next[i] = j;
            i++;
        } else {
            if (j != 0) {
                j = next[j-1];
            } else {
                next[i] = 0;
                i++;
            }
        }
    }
    return next;
}

// 使用第二种约定的 KMP 搜索
int kmpSearch2(char* text, char* pattern) {
    int n = strlen(text);
    int m = strlen(pattern);
    if (m == 0) return 0;
    int* next = getNext2(pattern);
    int i = 0, j = 0;
    while (i < n) {
        if (text[i] == pattern[j]) {
            i++;
            j++;
        }
        if (j == m) {
            free(next);
            return i - j;
        } else if (i < n && text[i] != pattern[j]) {
            if (j != 0) {
                j = next[j-1];
            } else {
                i++;
            }
        }
    }
    free(next);
    return -1;
}

总结

• 两种 next 数组约定都是正确的，选择取决于个人偏好或教材要求。
• 第一种约定（next[0] = -1）在代码中处理跳转更简洁。
• 第二种约定（next[0] = 0）更直观地表示最长公共前后缀的长度。

在实际应用中，建议根据上下文选择合适的约定。上述代码示例提供了两种实现，可供参考。