KMP算法之 next 数组的计算
/** * @brief 计算模式串的next数组（部分匹配表），并可视化计算过程 * @param pattern 模式串（待查找的基因片段） * @param next 输出参数：存储next数组（长度需≥模式串长度） */ void kmp_get_next(const char* pattern, int* next) { if (pattern == NULL || next == NULL) { printf("Error: 模式串或next数组指针为空！\n"); return; } int m = strlen(pattern); if (m == 0) { printf("Warning: 模式串为空，next数组为空！\n"); return; } // 初始化next数组 next[0] = -1; // 第一个位置固定为-1 int i = 0, j = -1; printf("===== next数组计算过程（模式串：%s）=====\n", pattern); printf("索引\t模式串字符\tj值\tnext[i]\n"); printf("----------------------------------------\n"); while (i < m - 1) { char c_i = pattern[i]; char c_j = (j >= 0) ? pattern[j] : '\0'; // 打印当前步骤（可视化） printf("%d\t%c\t\t%d\t", i, pattern[i], j); if (j == -1 || c_i == c_j) { i++; j++; next[i] = j; printf("next[%d] == %d\n", i, next[i]); // 输出当前next[i] } else { j = next[j]; // 回溯j printf("回溯j=%d\n", j); } } // 打印最终next数组 printf("----------------------------------------\n"); printf("最终next数组："); for (int k = 0; k < m; k++) { printf("%d ", next[k]); } printf("\n========================================\n"); }关于字符串匹配，我们可以使用暴力算法，将所有可能性全部试一次来匹配字符串，但是如果数据量很大，这种做法的效率非常低。所以我们可以使用 KMP 算法来提高字符串匹配的效率。改算法在匹配字符串之前，会先创建一个 next 数组用于提高字符串匹配的效率。上面是 next 数组的赋值代码。
以下是关于代码部分的解析：
next[x] 数组是存前 x 个字符串的前缀和后缀的匹配的最长字符串个数。例如： ABABA next[0] == -1; next[1] == 0; next[2] == 0; next[3] == 1; next[4] == 2;
我们看完代码过一遍基本流程会有一个问题（一开始我是有这样的疑问）：
为什么字符串匹配失败时，要让 j = next[j];
ABABAH这个字符串，匹配到H时，字符不匹配了，此时j＝3，i等于5，我们假设回溯到能回溯的最大值3，此时会陷入死循环。
因为j加到3了，说明字符H前三个我已经匹配好了，但是当前正在匹配的字符和字符串第四个字符不匹配。假设回溯最长匹配长度依旧是3（也就是回溯时，j=j），会依然不匹配。
next数组存的就是前n个字符的前后缀能匹配的最大字符个数，也就是说，在H之前匹配到的ABA是和字符串前三个字符是匹配的，也就是说，如果我想省点时间，可以直接从字符串的第4个开始重新匹配。但是问题是现在就是在第四个字符匹配失败了，因此绝对不能跳过字符串前3个开始匹配。直接回溯j不行，回溯j-1呢？每次都回溯j-1，也就是j＝j-1，理论上可行，但是效率极低。此时就需要判断前三个字符的前后缀能匹配到的最大字符数，因为现在字符本身已经先匹配到了3个字符，如果从头开始匹配浪费时间了，既然字符串H前面3个字符是匹配过了（也就是和字符串前3个字符是一样的），那么我们的目标就是找到在这3个字符里面能跳过的字符数，能跳过的字符数就是前后缀能匹配到的最大字符数（ABA是已经匹配到的，但是后面的字符B和要匹配的H不匹配，因此该位置的前后缀能匹配的最大字符数只会小于3 ）。next[j]存的数值前后缀最大匹配字符数就是字符串匹配时可以跳过的最大值。如果还是匹配不了，如此反复即可。
next[x]指的是前x个字符，前后缀匹配的最大字符数。
回溯之后，就是ABA 和 ABA，加粗部分是一样的，所以就不需要匹配第一个字符，从第一个字符往后匹配。如果是回溯 j == 2，ABA 和 ABA，加粗部分AB和BA显然不匹配。这就是next[x] 数组的作用，当我已经匹配了 x 个字符，我只需要找到前 x 个字符串的前后缀匹配最大字符数即可，该值就是重新匹配时能跳过的字符数。
此时，j＝next[j]也就是j等于匹配时可以跳过的字符个数。如果j＝0，那么str[j]＝str[0]，恰好就是跳过0个字符;如果是j＝1，那么str[j]＝str[1]，此时恰好就是跳过1个字符(也就是只跳过str[0])。依次类推，j的值恰好就是跳过字符串数的值