Dustin Boston

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.

Source Code Listing

code.ts 

/**
 * @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;
}

code_test.ts 

import {describe, test, expect} 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);
});

Tags

[End]