Dustin Boston

/*!
 * @file Implements the brute-force longest common prefix (LCP) algorithm.
 * @author Dustin Boston <mail@dustin.boston>
 * @see R. Sedgewick, K. Wayne. "Context," in _Algorithms_, 4th ed., Addison
 * Wesley, 2011, ch. 6, pp. 875.
 */

/**
 * Brute-force longest common prefix (LCP). Finds the longest substring that is
 * a prefix of both strings.
 *
 * @param a The first string to test
 * @param b The second string to test
 * @returns Index of the final character in the suffix.
 */
export function longestCommonPrefix(a: string, b: string) {
  const n = Math.min(a.length, b.length);
  for (let i = 0; i < n; i++) {
    if (a.codePointAt(i) !== b.codePointAt(i)) return i;
  }

  return n;
}

// Usage
(() => {
  const a = "acctgttaac";
  const b = "accgttaa";

  const matchEndIndex = longestCommonPrefix(a, b);

  if (matchEndIndex !== 3) {
    console.log("Did not find expected matchEndIndex");
    return;
  }

  console.log(`Longest common prefix: ${a.slice(0, matchEndIndex)}`);
})();

import {longestCommonPrefix} from "../../../../data/algorithms/src/longest_common_prefix.ts";
import {assertEquals} from "$assert";

test(function testLongestCommonPrefix() {
  const a = "acctgttaac";
  const b = "accgttaa";

  const matchEndIndex = longestCommonPrefix(a, b);
  assertEquals(matchEndIndex, 3); // A[0..3] == acc
});