Press n or j to go to the next uncovered block, b, p or k for the previous block.
| 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 | 1x 1x 11x 11x 11x 11x 11x 11x 11x 11x 11x 11x 165x 165x 3440x 3440x 233x 3440x 3207x 3207x 3440x 78x 78x 78x 3440x 165x 11x 11x | import { create2dArray } from './create2d-array.ts';
/**
* Options for configuring the longest common substring calculation.
* @group String
* @category Fuzzy Match
*/
export type LongestCommonSubstringOptions = {
/** compare the two strings in case insensitive mode */
caseInsensitive?: boolean;
};
/**
* Implementation of [Longest Common Substring](https://en.wikipedia.org/wiki/Longest_common_substring_problem) algorithm.
*
* Returns the longest possible substring that is substring of both of given strings.
* @param string1 - First string.
* @param string2 - Second string.
* @returns A string that is common to both strings such that there is no
* common substring with size greater than the length of the string.
* @group String
* @category Fuzzy Match
*/
export function longestCommonSubstring(
string1: string,
string2: string,
{ caseInsensitive = false }: LongestCommonSubstringOptions = {},
): string {
const ci1 = caseInsensitive ? string1.toLocaleLowerCase() : string1;
const ci2 = caseInsensitive ? string2.toLocaleLowerCase() : string2;
const comparisons = create2dArray(ci1.length + 1, ci2.length + 1, 0);
let maxSubStrLength = 0;
let lastMaxSubStrIndex = -1;
for (let i = 0; i < ci1.length; ++i) {
const c1 = ci1.charAt(i);
for (let j = 0; j < ci2.length; ++j) {
const c2 = ci2.charAt(j);
if (c1 === c2) {
comparisons[i][j] = i > 0 && j > 0 ? comparisons[i - 1][j - 1] + 1 : 1;
} else {
comparisons[i][j] = 0;
}
if (comparisons[i][j] > maxSubStrLength) {
maxSubStrLength = comparisons[i][j];
lastMaxSubStrIndex = i;
}
}
}
return string1.slice(lastMaxSubStrIndex - maxSubStrLength + 1, lastMaxSubStrIndex + 1);
}
|