Naive String Matcher

The naive string matching algorithm finds a pattern in a text. It uses brute force to check every position. It works by moving the pattern across the text from left to right. At each position, the algorithm compares the pattern’s characters to the text’s characters. If every character matches, the position is valid. Its takes O((n - m + 1) m) time.

/**
 * @file Naive String Matcher
 * @author Dustin Boston
 * @see Cormen, T, Leiserson, C, Rivest, R, and Stein, C. (2001).
 *   Introduction to Algorithms. (2nd ed). The MIT Press.
 */
export function naiveStringMatcher(text: string, pattern: string) {
  const n = text.length;
  const m = pattern.length;

  let count = 0;

  for (let s = 0; s <= n - m; s++) {
    const a = pattern.slice(0, m);
    const b = text.slice(s, s + m);
    if (a === b) {
      count++;
    }
  }

  return count;
}

import { expect, test } from "bun:test";
import { naiveStringMatcher } from "./code";

test(`find pattern "aab" in "acaabc"`, () => {
  const actual = naiveStringMatcher("acaabc", "aab");
  const expected = 1;
  expect(actual).toEqual(expected);
});

Myers Diff

Negative Array

Docs

computer-science.dev

Title here

Naive String Matcher