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时字符不匹配了此时j3i等于5我们假设回溯到能回溯的最大值3此时会陷入死循环。因为j加到3了说明字符H前三个我已经匹配好了但是当前正在匹配的字符和字符串第四个字符不匹配。假设回溯最长匹配长度依旧是3也就是回溯时jj会依然不匹配。next数组存的就是前n个字符的前后缀能匹配的最大字符个数也就是说在H之前匹配到的ABA是和字符串前三个字符是匹配的也就是说如果我想省点时间可以直接从字符串的第4个开始重新匹配。但是问题是现在就是在第四个字符匹配失败了因此绝对不能跳过字符串前3个开始匹配。直接回溯j不行回溯j-1呢每次都回溯j-1也就是jj-1理论上可行但是效率极低。此时就需要判断前三个字符的前后缀能匹配到的最大字符数因为现在字符本身已经先匹配到了3个字符如果从头开始匹配浪费时间了既然字符串H前面3个字符是匹配过了也就是和字符串前3个字符是一样的那么我们的目标就是找到在这3个字符里面能跳过的字符数能跳过的字符数就是前后缀能匹配到的最大字符数ABA是已经匹配到的但是后面的字符B和要匹配的H不匹配因此该位置的前后缀能匹配的最大字符数只会小于3 。next[j]存的数值前后缀最大匹配字符数就是字符串匹配时可以跳过的最大值。如果还是匹配不了如此反复即可。next[x]指的是前x个字符前后缀匹配的最大字符数。回溯之后就是ABA 和 ABA加粗部分是一样的所以就不需要匹配第一个字符从第一个字符往后匹配。如果是回溯 j 2ABA 和 ABA加粗部分AB和BA显然不匹配。这就是next[x] 数组的作用当我已经匹配了 x 个字符我只需要找到前 x 个字符串的前后缀匹配最大字符数即可该值就是重新匹配时能跳过的字符数。此时jnext[j]也就是j等于匹配时可以跳过的字符个数。如果j0那么str[j]str[0]恰好就是跳过0个字符;如果是j1那么str[j]str[1]此时恰好就是跳过1个字符(也就是只跳过str[0])。依次类推j的值恰好就是跳过字符串数的值如果有什么问题欢迎讨论