用JS 后缀数组方法写一个遍历主串所有子串 返回重复子串和重复次数
时间: 2024-02-02 16:02:44 浏览: 20
以下是使用 JS 后缀数组方法实现遍历主串所有子串并返回重复子串和重复次数的代码:
```javascript
function findRepeatSubstr(str) {
let suffixArr = buildSuffixArray(str); // 构建后缀数组
let maxRepeatCount = 0; // 最大重复次数
let repeatSubstrs = new Set(); // 重复子串集合
for (let i = 0; i < suffixArr.length - 1; i++) {
let j = i + 1;
let repeatCount = 0; // 当前重复次数
// 比较相邻后缀
while (suffixArr[i].startsWith(suffixArr[j]) || suffixArr[j].startsWith(suffixArr[i])) {
repeatCount++;
j++;
// 更新最大重复次数和重复子串集合
if (repeatCount > maxRepeatCount) {
maxRepeatCount = repeatCount;
repeatSubstrs.clear();
repeatSubstrs.add(suffixArr[i].substring(0, repeatCount));
} else if (repeatCount === maxRepeatCount) {
repeatSubstrs.add(suffixArr[i].substring(0, repeatCount));
}
}
}
return { repeatSubstrs: Array.from(repeatSubstrs), maxRepeatCount };
}
// 构建后缀数组
function buildSuffixArray(str) {
let suffixes = [];
for (let i = 0; i < str.length; i++) {
suffixes.push(str.slice(i));
}
suffixes.sort();
let suffixArr = suffixes.map(suffix => str.length - suffix.length + 1);
return suffixArr;
}
```
该函数接受一个字符串作为参数,并返回一个对象,包含重复子串和重复次数。其中,重复子串以数组形式返回,重复次数为一个整数。
例如,对于字符串 `"banana"`,调用 `findRepeatSubstr("banana")` 将返回以下结果:
```javascript
{ repeatSubstrs: ['an'], maxRepeatCount: 2 }
```
表示字符串中有一个重复子串 `"an"`,重复了两次。