Longest Common Prefix /*! * @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. */ 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)}`); })(); Run Code