diff options
| author | Ty Dunn <ty@tydunn.com> | 2023-06-16 15:56:01 -0700 |
|---|---|---|
| committer | GitHub <noreply@github.com> | 2023-06-16 15:56:01 -0700 |
| commit | c196431ff1de014827066e3a04c39438c34ebe3d (patch) | |
| tree | a91625915ea31f00b0991ff3f333925e17bab5a4 /extension/src/util | |
| parent | 085c6f846715d55d6638c73d34886ddf2a26d1b5 (diff) | |
| parent | 55611ef0b6ca014ff091a1cd18fb749ab210b3ec (diff) | |
| download | sncontinue-c196431ff1de014827066e3a04c39438c34ebe3d.tar.gz sncontinue-c196431ff1de014827066e3a04c39438c34ebe3d.tar.bz2 sncontinue-c196431ff1de014827066e3a04c39438c34ebe3d.zip | |
Merge branch 'main' into too-large
Diffstat (limited to 'extension/src/util')
| -rw-r--r-- | extension/src/util/lcs.ts | 30 |
1 files changed, 30 insertions, 0 deletions
diff --git a/extension/src/util/lcs.ts b/extension/src/util/lcs.ts new file mode 100644 index 00000000..17ea63f9 --- /dev/null +++ b/extension/src/util/lcs.ts @@ -0,0 +1,30 @@ +export function longestCommonSubsequence(a: string, b: string) { + const lengths: number[][] = []; + for (let i = 0; i <= a.length; i++) { + lengths[i] = []; + for (let j = 0; j <= b.length; j++) { + if (i === 0 || j === 0) { + lengths[i][j] = 0; + } else if (a[i - 1] === b[j - 1]) { + lengths[i][j] = lengths[i - 1][j - 1] + 1; + } else { + lengths[i][j] = Math.max(lengths[i - 1][j], lengths[i][j - 1]); + } + } + } + let result = ""; + let x = a.length; + let y = b.length; + while (x !== 0 && y !== 0) { + if (lengths[x][y] === lengths[x - 1][y]) { + x--; + } else if (lengths[x][y] === lengths[x][y - 1]) { + y--; + } else { + result = a[x - 1] + result; + x--; + y--; + } + } + return result; +} |