带前缀表的 KMP 子串搜索

功能说明

该示例实现 Knuth-Morris-Pratt 子串搜索。buildPrefixTable 计算模式串每个前缀的最长真前缀后缀长度，searchAll 利用该表在文本失配时跳过不可能匹配的位置，时间复杂度为文本长度加模式长度。返回所有匹配的起始下标，包括相互重叠的匹配，适合日志关键字扫描、DNA 序列查找或流式协议分隔符定位。

关键代码

前缀表构建时维护当前最长 border 长度，字符相等则扩展并写入表，失配则回退到前一个 border，直到可以继续或长度归零。搜索阶段 matched 表示已匹配的字符数，失配时按表回退而不是回到零；每完成一次匹配，把起点写入结果，再用最后一位的 border 继续，从而发现重叠匹配。两个函数都先做字符串类型断言。

使用注意

下标按 UTF-16 码元计算，不是 Unicode 码点，包含 emoji 或组合字符时返回位置可能与视觉字符不一致；需要码点级搜索应先把文本转为数组。空前模式按照数学约定在每个位置都匹配，包括文本末尾，调用方若不希望产生这么多结果应提前排除。算法区分大小写且不做 Unicode 规范化。该实现不返回匹配长度，但可由模式长度推导。

验证方式

对 ababaca 断言前缀表为预期数组；在重复文本中搜索短模式，检查重叠匹配下标全部返回；测试无匹配返回空数组、模式长于文本返回空数组、空模式返回从零到文本长度的所有下标；用 emoji 文本验证下标按码元计数；传入非字符串参数断言 TypeError。

代码示例

function assertString(value: unknown, name: string): asserts value is string {
  if (typeof value !== "string") throw new TypeError(name + " must be a string");
}

export function buildPrefixTable(pattern: string): number[] {
  assertString(pattern, "pattern");
  const table = new Array<number>(pattern.length).fill(0);
  let length = 0;
  for (let index = 1; index < pattern.length;) {
    if (pattern[index] === pattern[length]) {
      length += 1;
      table[index] = length;
      index += 1;
    } else if (length > 0) {
      length = table[length - 1];
    } else {
      table[index] = 0;
      index += 1;
    }
  }
  return table;
}

export function searchAll(text: string, pattern: string): number[] {
  assertString(text, "text");
  assertString(pattern, "pattern");
  if (pattern.length === 0) {
    return Array.from({ length: text.length + 1 }, (_, index) => index);
  }
  const table = buildPrefixTable(pattern);
  const matches: number[] = [];
  let matched = 0;
  for (let index = 0; index < text.length; index += 1) {
    while (matched > 0 && text[index] !== pattern[matched]) {
      matched = table[matched - 1];
    }
    if (text[index] === pattern[matched]) matched += 1;
    if (matched === pattern.length) {
      matches.push(index - matched + 1);
      matched = table[matched - 1];
    }
  }
  return matches;
}