# @algorithm.ts/lcs
> Find the longest common subsequence.
Latest version **4.0.6** (published 2026-03-23) · MIT license · 0 weekly downloads
## Install
```sh
npm install @algorithm.ts/lcs
pnpm add @algorithm.ts/lcs
yarn add @algorithm.ts/lcs
bun add @algorithm.ts/lcs
```
## Health
**Score 60/100 (C)** — status: stable.
Positive: has types; esm support; no vulnerabilities; high quality score.
Warnings: low downloads.
## Facts
| | |
|---|---|
| Version | 4.0.6 |
| Published | 2026-03-23 |
| First published | 2022-02-22 |
| Weekly downloads | 0 |
| License | MIT |
| TypeScript types | bundled |
| Module format | ESM + CommonJS |
| Dependencies | 0 |
| Unpacked size | 59.7 KB |
| Known vulnerabilities | 0 |
| Install scripts | no |
| GitHub stars | 117 |
| Author | guanghechen |
| Maintainers | lemonclown |
| Keywords | algorithm, lcs, longest common subsequence |
## Links
- npm: https://www.npmjs.com/package/@algorithm.ts/lcs
- Repository: https://github.com/guanghechen/algorithm.ts.git#@algorithm.ts
- Homepage: https://github.com/guanghechen/algorithm.ts/tree/@algorithm.ts/lcs@4.0.5/packages/lcs#readme
- Issues: https://github.com/guanghechen/algorithm.ts/issues
- npm.io page: https://npm.io/package/@algorithm.ts/lcs
## Recent versions
- 4.0.6 (latest) — 2026-03-23
- 4.0.5 — 2024-10-06
- 4.0.4 — 2024-09-14
- 4.0.3 — 2024-06-11
- 4.0.2 — 2024-06-04
- 4.0.1 — 2024-05-29
- 4.0.0 — 2024-03-30
- 3.1.1 — 2023-06-10
- 3.1.0 — 2023-05-13
- 3.0.0 — 2023-04-02
- 3.0.0-alpha.8 — 2023-03-11
- 3.0.0-alpha.7 — 2023-01-09
- 3.0.0-alpha.6 — 2023-01-07
- 3.0.0-alpha.5 — 2023-01-07
- 3.0.0-alpha.4 — 2023-01-07
- … 21 more at https://npm.io/package/@algorithm.ts/lcs/versions
## README
A typescript implementation to find the **lcs** (Longest Common Subsequence).
This package provide three different implementation of lcs algorithm. To measure the complexity of
these algorithms, let the $N_1$ and $N_2$ be the subsequences length of two sequences respectively.
And let $L$ be the length of the longest common subsequences, then the $D = 2L - N_1 - N_2$.
1. `myers_lcs(N1: number, N2: number, equals: (x: number, y: number) => boolean): [x: number, y: number][]`:
The vanilla algorithm introduced by this paper
[_An O(ND) Difference Algorithm and Its Variations_](https://mailserver.org/diff2.pdf).
- Time complexity: $O((N_1 + N_2) \times D)$
- Memory complexity: $O(N_1 \times N_2)$
2. `myers_lcs_linear_space(N1: number, N2: number, equals: (x: number, y: number) => boolean): [x: number, y: number][]`:
The linear space refinement algorithm from
[_An O(ND) Difference Algorithm and Its Variations_](https://mailserver.org/diff2.pdf).
- Time complexity: $O((N_1 + N_2) * D)$
- Memory complexity: $O(N_1 + N_2)$
3. `lcs_dp(N1: number, N2: number, equals: (x: number, y: number) => boolean): [x: number, y: number][]`
This implementation is based on dynamic programming, and can find the minimal lexicographical
lcs.
- Time complexity: $O(N_1 \times N_2)$
- Memory complexity: $O(N_1 \times N_2)$
The following definition is quoted from Wikipedia
(https://en.wikipedia.org/wiki/Longest_common_subsequence_problem):
> The longest common subsequence (LCS) problem is the problem of finding the longest subsequence
> common to all sequences in a set of sequences (often just two sequences). It differs from the
> longest common substring problem: unlike substrings, subsequences are not required to occupy
> consecutive positions within the original sequences. The longest common subsequence problem is a
> classic computer science problem, the basis of data comparison programs such as the diff utility,
> and has applications in computational linguistics and bioinformatics. It is also widely used by
> revision control systems such as Git for reconciling multiple changes made to a
> revision-controlled collection of files.
## Install
- npm
```bash
npm install --save @algorithm.ts/lcs
```
- pnpm
```bash
pnpm add @algorithm.ts/lcs
```
## Usage
- Basic
```typescript
import { lcs_dp, lcs_myers_size } from '@algorithm.ts/lcs'
const s1: number[] = [1, 2, 3, 4, 6, 6, 7, 8, 6]
const s2: number[] = [2, 3, 4, 7, 9, 8, 2, 3, 5, 2]
lcs_myers_size(s1.length, s2.length, (x, y) => s1[x] === s2[y]) // => 5
lcs_dp(s1.length, s2.length, (x, y) => s1[x] === s2[y])
// => [ [1, 0], [2, 1], [3, 2], [6, 3], [7, 5] ]
//
// Here is why:
//
// 0 1 2 3 4 5 6 7 8 9
// s1: 1 2 3 4 6 6 7 8 6
// s2: 2 3 4 7 9 8 2 3 5 2
//
// s1[1] <----> s2[0]
// s1[2] <----> s2[1]
// s1[3] <----> s2[2]
// s1[6] <----> s2[3]
// null <----> s2[4]
// s1[7] <----> s2[5]
// null <----> s2[6]
// null <----> s2[7]
// null <----> s2[8]
// null <----> s2[9]
```
## Related
- [An O(ND) Difference Algorithm and Its Variations](https://mailserver.org/diff2.pdf).
- [最长公共子序列（LCS） | 光和尘][lcs]
- [Longest common subsequence problem | Wikipedia][wikipedia-lcs]
[homepage]:
https://github.com/guanghechen/algorithm.ts/tree/@algorithm.ts/lcs@4.0.5/packages/lcs#readme
[lcs]: https://me.guanghechen.com/post/algorithm/lcs/
[wikipedia-lcs]: https://en.wikipedia.org/wiki/Longest_common_subsequence_problem
---
_Source: https://npm.io/package/@algorithm.ts/lcs · Machine-readable twin of the npm.io package page. Health data is recomputed on every publish._
