KMP Substring Search With Prefix Table

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;
}