为什么 KMP 字符串匹配的整体时间复杂度是 O(n+m)，文本指针为什么从不回退？

前缀函数如何实现线性匹配

前缀函数π[i]是模式串在索引i处的最长真前后缀长度。例如模式'abcabcd'的π为[0,0,0,1,2,3,0]，π[5]=3表示前缀'abc'也是后缀'abc'。匹配时，若text[i]与pattern[j]失配且j>0，则j=π[j-1]，将模式向右滑动，同时保留已匹配的前缀部分，避免文本字符被重复比较。

复杂度证明：设文本长n，模式长m。主循环中i每次增加1，共进行n轮。模式指针j在匹配成功时增加1，最多增加n次；失配时j回退，每次回退都因先前至少一次匹配成功积累了“信用”，所以j的总减少次数不超过总增加次数。因此循环内所有操作次数为O(n)，加上预处理π的O(m)，总复杂度O(n+m)。

function kmpSearch(text, pattern) {
  const m = pattern.length;
  const pi = new Array(m).fill(0);
  for (let i = 1; i < m; i++) {
    let j = pi[i - 1];
    while (j > 0 && pattern[i] !== pattern[j]) j = pi[j - 1];
    if (pattern[i] === pattern[j]) j++;
    pi[i] = j;
  }
  const matches = [];
  let j = 0;
  for (let i = 0; i < text.length; i++) {
    while (j > 0 && text[i] !== pattern[j]) j = pi[j - 1];
    if (text[i] === pattern[j]) j++;
    if (j === m) {
      matches.push(i - m + 1);
      j = pi[j - 1];
    }
  }
  return { matches };
}
console.log(JSON.stringify(kmpSearch('abcabcabcabc', 'abcabc')));
console.log(JSON.stringify(kmpSearch('aaaaab', 'aaaa')));
console.log(JSON.stringify(kmpSearch('abababc', 'ababc')));

{"matches":[0,3,6]}
{"matches":[0,1]}
{"matches":[2]}

长日志中搜寻重复模式

假设系统日志文件有10^6个ASCII字符，需要找出模式“ababac”出现的位置。暴力匹配在每次失配后文本指针回退，最坏比较次数接近6×10^6。改用KMP：预处理模式串的π数组，然后一遍扫描文本，i从0递增到末尾，每次失配j回退但i不动，总比较次数为O(n+m)。

此场景的关键在于日志中可能出现“ababab”这样的长重复前缀，失配时能一次移动多个位置。KMP利用π数组跳过那些已知不可能匹配的位置，使得文本中每个字符只被比较常数次，因此总时间与日志长度线性相关，满足实时处理需求。

线性正确性的边界条件

KMP线性性不依赖具体数据，但存在常数差异。当模式为全同字符如'aaaaa'时，π数组为[0,1,2,3,4]，失配时j每次只会回退1，但匹配时j增加快，回退次数占比仍不超过50%，总比较次数约2n，依然是O(n)。真正的风险在于模式中存在大量不同border，导致π链变长，但链长受模式长度m限制，总回退次数依然≤n。

若模式或文本长度极短（如n≤1），KMP与暴力并无区别，此时不必要引入预处理开销。另外，若模式中包含通配符或需要动态更新，KMP框架不再适用，需改用Aho-Corasick或扩展算法，因为π依赖于静态模式。工程中应评估数据规模与模式变更频率，避免为短串重复计算π。

容易答错的地方

误认为文本指针从不回退意味着从不重复比较

文本指针i确实不回退，但同一文本字符可能被多次比较（例如失配后j回退再比较同一位）。不过这种重复次数受π跳转限制，摊还后总次数仍为O(n)，这正是线性复杂度的来源。

认为模式指针回退会造成O(nm)

模式指针j回退到π[j-1]跳过了很多无效比对，并非每次只退一格。即使退多步，总回退次数≤成功匹配次数≤n，所以均摊后线性。关键是把回退视为“利用已比较信息的跳跃”，而不是重置。

面试官还会怎么问？

把知识连起来