KMPKnuth-Morris-Pratt算法是一种高效的字符串匹配算法用于在主串文本中查找模式串模式首次出现的位置。其核心思想是当匹配失败时利用已匹配部分的信息通过一个预先计算好的next数组或称部分匹配表来决定模式串下一次比较的位置从而避免主串指针的回退将时间复杂度从朴素算法的 O(m*n) 优化至 O(mn) 。###核心原理最长公共前后缀与next数组KMP算法的关键在于理解最长公共前后缀。对于模式串P的每个前缀子串P[0...i]其最长公共前后缀的长度不包括自身被记录在next[i]数组中。这个数组指导匹配失败时模式串指针j应该回退到的位置 。next数组定义示例模式串P ABABC前缀子串最长公共前后缀长度next值 (通常右移一位next[0] -1)A0next[0] -1AB0next[1] 0ABA1 (A)next[2] 1ABAB2 (AB)next[3] 2ABABC0next[4] 0算法步骤预处理计算模式串P的next数组。匹配使用双指针i主串索引和j模式串索引进行匹配。若字符相等则i,j。若字符不等且j 0则令j next[j]模式串指针根据next数组回退。若字符不等且j 0则i。当j等于模式串长度时匹配成功。代码实现####1. C实现#include iostream #include vector #include string using namespace std; // 计算 next 数组 vectorint getNext(const string pattern) { int m pattern.size(); vectorint next(m, 0); next[0] -1; // 通常将 next[0] 设为 -1 作为哨兵 int i 0, j -1; while (i m - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; next[i] j; // 标准 next 数组赋值 } else { j next[j]; // 不匹配时j 回退 } } return next; } // KMP 搜索函数 int kmpSearch(const string text, const string pattern) { int n text.size(), m pattern.size(); if (m 0) return 0; // 空模式串 vectorint 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]; // 利用 next 数组跳过不必要的比较 } } if (j m) { return i - j; // 返回匹配的起始位置 } return -1; // 未找到 } int main() { string text ABABABABC; string pattern ABABC; int pos kmpSearch(text, pattern); if (pos ! -1) { cout Pattern found at index: pos endl; } else { cout Pattern not found. endl; } return 0; }2. Java 实现public class KMP { // 计算 next 数组 public static int[] getNext(String pattern) { int m pattern.length(); int[] next new int[m]; next[0] -1; int i 0, j -1; while (i m - 1) { if (j -1 || pattern.charAt(i) pattern.charAt(j)) { i; j; next[i] j; } else { j next[j]; } } return next; } // KMP 搜索函数 public static int kmpSearch(String text, String pattern) { int n text.length(), m pattern.length(); if (m 0) return 0; int[] next getNext(pattern); int i 0, j 0; while (i n j m) { if (j -1 || text.charAt(i) pattern.charAt(j)) { i; j; } else { j next[j]; } } if (j m) { return i - j; } return -1; } public static void main(String[] args) { String text ABABABABC; String pattern ABABC; int pos kmpSearch(text, pattern); if (pos ! -1) { System.out.println(Pattern found at index: pos); } else { System.out.println(Pattern not found.); } } }next数组的优化 (nextval数组)在某些情况下标准next数组仍有优化空间。例如模式串P AAAAAB当P[4]匹配失败时根据next[4]3会回退到P[3]而P[3]和P[4]字符相同必然再次失败。优化的nextval数组可以避免这种连续失败 。nextval数组构造逻辑在计算next[i]后检查P[i]是否等于P[next[i]]。若相等则nextval[i] nextval[next[i]]否则nextval[i] next[i]。// 计算优化的 nextval 数组 (C示例) vectorint getNextVal(const string pattern) { int m pattern.size(); vectorint nextval(m, 0); nextval[0] -1; int i 0, j -1; while (i m - 1) { if (j -1 || pattern[i] pattern[j]) { i; j; // 优化点若回退后字符相同则继续取回退位置的nextval值 if (pattern[i] ! pattern[j]) { nextval[i] j; } else { nextval[i] nextval[j]; } } else { j nextval[j]; } } return nextval; }算法对比特性朴素暴力匹配算法KMP算法时间复杂度O(m*n)O(mn)空间复杂度O(1)O(m) (用于存储next数组)核心思想主串和模式串指针每次失败后都回退主串指针不回退模式串指针根据next数组回退适用场景短文本、简单场景长文本、需要高效匹配的场景KMP算法通过预处理模式串将匹配过程中的信息利用到极致是理解更复杂字符串匹配算法如Boyer-Moore, Sunday算法的重要基础 。参考来源KMP算法的原理和C实现KMP算法原理及实现kmp算法原理及实现KMP 看毛片算法原理及其实现KMP算法原理及实现