Longest Common Prefix

An algorithm for finding the longest common prefix among a set of strings.

Time complexity is Linear, i.e. O(n)
Space complexity is Constant, i.e. O(1)

Source Code Listing

code.ts

/*!
 * @file Implements the brute-force longest common prefix (LCP) algorithm.
 * @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;
}

code_test.ts

import {describe, it, expect} from "bun:test";
import {longestCommonPrefix} from "./code";

describe("Longest Common Prefix", () => {
  it("testLongestCommonPrefix", () => {
    const a = "acctgttaac";
    const b = "accgttaa";

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

Tags: