diff options
| author | Nate Sesti <sestinj@gmail.com> | 2023-06-16 14:34:30 -0700 |
|---|---|---|
| committer | Nate Sesti <sestinj@gmail.com> | 2023-06-16 14:34:30 -0700 |
| commit | b740c5bf216b63dbb2ffa88f8385e9795aa57403 (patch) | |
| tree | 490ec7dff021b5f9f1837b1d37138bd02a6be54b /extension/src/util | |
| parent | f6d940dead08bc065de7717d440bd98d8fc60c79 (diff) | |
| download | sncontinue-b740c5bf216b63dbb2ffa88f8385e9795aa57403.tar.gz sncontinue-b740c5bf216b63dbb2ffa88f8385e9795aa57403.tar.bz2 sncontinue-b740c5bf216b63dbb2ffa88f8385e9795aa57403.zip | |
Capturing command line prompt
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; +} |