用JS 倍增法创建后缀数组方法写一个遍历主串所有子串 返回重复子串和重复次数
时间: 2024-05-13 18:19:27 浏览: 18
好的,以下是用JS实现的后缀数组和遍历主串所有子串的代码:
```javascript
// 定义后缀数组
function createSuffixArray(str) {
const n = str.length;
const suffixArr = new Array(n);
const rank = new Array(n);
// 初始化rank数组
for (let i = 0; i < n; i++) {
suffixArr[i] = i;
rank[i] = str.charCodeAt(i) - 97;
}
// 用于排序的辅助数组,bucket[i]表示rank值为i的后缀的数量
const bucket = new Array(n);
for (let k = 1; k < n; k *= 2) {
// 根据第k个字符对后缀进行排序
bucket.fill(0);
for (let i = 0; i < n; i++) {
bucket[rank[(suffixArr[i] + k) % n]]++;
}
for (let i = 1; i < n; i++) {
bucket[i] += bucket[i - 1];
}
for (let i = n - 1; i >= 0; i--) {
const j = (suffixArr[i] + k) % n;
bucket[rank[j]]--;
suffixArr[bucket[rank[j]]] = suffixArr[i];
}
// 根据前k个字符对后缀进行排序
bucket.fill(0);
for (let i = 0; i < n; i++) {
bucket[rank[suffixArr[i]]]++;
}
for (let i = 1; i < n; i++) {
bucket[i] += bucket[i - 1];
}
for (let i = n - 1; i >= 0; i--) {
bucket[rank[suffixArr[i]]]--;
const j = (suffixArr[i] - k + n) % n;
rank[j] = bucket[rank[suffixArr[i]]];
}
}
return suffixArr;
}
// 遍历主串所有子串并返回重复子串和重复次数
function findDuplicateSubstrings(str) {
const suffixArr = createSuffixArray(str);
const n = str.length;
const lcpArr = new Array(n);
let ans = '';
let cnt = 0;
// 计算LCP数组
for (let i = 0, k = 0; i < n; i++) {
if (rank[i] === 0) {
lcpArr[rank[i]] = 0;
continue;
}
const j = suffixArr[rank[i] - 1];
while (i + k < n && j + k < n && str[i + k] === str[j + k]) {
k++;
}
lcpArr[rank[i]] = k;
k = Math.max(k - 1, 0);
}
// 遍历所有子串
for (let i = 1; i < n; i++) {
if (lcpArr[i] > 0) {
const len = lcpArr[i];
const subStr = str.substr(suffixArr[i], len);
if (subStr === ans) {
cnt++;
} else if (subStr.length > ans.length) {
ans = subStr;
cnt = 1;
}
}
}
return { substring: ans, count: cnt };
}
```
其中,`createSuffixArray`函数用于创建后缀数组,`findDuplicateSubstrings`函数用于遍历所有子串并返回重复子串和重复次数。你可以直接调用该函数,传入主串作为参数即可。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)