Spaces:
Running
Running
File size: 2,071 Bytes
15b27a1 | 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 58 59 60 61 62 63 64 | "use strict";
Object.defineProperty(exports, "__esModule", {
value: true
});
exports.findRepeatedSubsequences = findRepeatedSubsequences;
/**
* Copyright (c) Microsoft Corporation.
*
* Licensed under the Apache License, Version 2.0 (the "License");
* you may not use this file except in compliance with the License.
* You may obtain a copy of the License at
*
* http://www.apache.org/licenses/LICENSE-2.0
*
* Unless required by applicable law or agreed to in writing, software
* distributed under the License is distributed on an "AS IS" BASIS,
* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
* See the License for the specific language governing permissions and
* limitations under the License.
*/
function findRepeatedSubsequences(s) {
const n = s.length;
const result = [];
let i = 0;
const arraysEqual = (a1, a2) => {
if (a1.length !== a2.length) return false;
for (let j = 0; j < a1.length; j++) {
if (a1[j] !== a2[j]) return false;
}
return true;
};
while (i < n) {
let maxRepeatCount = 1;
let maxRepeatSubstr = [s[i]]; // Initialize with the element at index i
let maxRepeatLength = 1;
// Try substrings of length from 1 to the remaining length of the array
for (let p = 1; p <= n - i; p++) {
const substr = s.slice(i, i + p); // Extract substring as array
let k = 1;
// Count how many times the substring repeats consecutively
while (i + p * k <= n && arraysEqual(s.slice(i + p * (k - 1), i + p * k), substr)) k += 1;
k -= 1; // Adjust k since it increments one extra time in the loop
// Update the maximal repeating substring if necessary
if (k > 1 && k * p > maxRepeatCount * maxRepeatLength) {
maxRepeatCount = k;
maxRepeatSubstr = substr;
maxRepeatLength = p;
}
}
// Record the substring and its count
result.push({
sequence: maxRepeatSubstr,
count: maxRepeatCount
});
i += maxRepeatLength * maxRepeatCount; // Move index forward
}
return result;
} |