遍历主串所有子串 找到重复子串的重复次数 有什么高效算法
时间: 2024-05-25 21:12:47 浏览: 124
这个问题其实就是求最长重复子串的问题,可以使用后缀数组和最长公共前缀数组来解决。具体算法如下:
1. 构建原始字符串的后缀数组。
2. 根据后缀数组构建最长公共前缀数组LCP。
3. 对于每个LCP值大于0的相邻后缀,它们的最长公共前缀就是一个重复子串。
4. 统计所有重复子串的重复次数。
这个算法的时间复杂度为O(nlogn),其中n为字符串长度。具体实现可以参考相关算法书籍或者网上资料。
相关问题
帮我用JS写一个遍历主串所有子串 找到重复子串的重复次数 的高效算法
可以使用哈希表来实现高效算法,具体思路如下:
1. 构建一个哈希表,键为子串,值为该子串出现的次数。
2. 遍历主串的所有子串,将每个子串作为键加入哈希表中,如果该子串已经在哈希表中存在,则将该子串对应的值加一。
3. 遍历完所有子串后,遍历哈希表,找到值大于1的键,即为重复子串,输出该子串和对应的值。
以下是实现代码:
```
function findRepeatedSubstr(str) {
const len = str.length;
const map = new Map();
for (let i = 0; i < len; i++) {
for (let j = i + 1; j <= len; j++) {
const substr = str.slice(i, j);
if (!map.has(substr)) {
map.set(substr, 1);
} else {
map.set(substr, map.get(substr) + 1);
}
}
}
const result = [];
for (const [key, value] of map.entries()) {
if (value > 1) {
result.push([key, value]);
}
}
return result;
}
const str = "abcabcabc";
const result = findRepeatedSubstr(str);
console.log(result); // [["abc", 3], ["ab", 2], ["bc", 2], ["ca", 2]]
```
该算法的时间复杂度为 $O(n^2)$,空间复杂度为 $O(n^2)$。如果需要更高效的算法,可以尝试使用后缀数组或者哈希函数等数据结构和算法。
递归算法获取字符串的所有子串
递归算法获取字符串的所有子串可以通过以下步骤实现:
1. 定义递归函数,传入两个参数:原始字符串和当前子串的起始位置。
2. 在递归函数中,使用循环遍历从当前起始位置开始的所有子串。具体来说,从起始位置开始,每次增加一个字符,直到达到字符串末尾。
3. 对于每个子串,将其添加到结果列表中。
4. 递归调用函数,将起始位置增加一位,继续遍历以当前起始位置开始的所有子串。
5. 最终返回结果列表。
以下是一个Python实现示例:
```python
def get_all_substrings(s, start=0):
if start == len(s):
return []
substrings = []
for i in range(start, len(s)):
substrings.append(s[start:i+1])
return substrings + get_all_substrings(s, start+1)
s = "abc"
print(get_all_substrings(s)) # ["a", "ab", "abc", "b", "bc", "c"]
```
在这个示例中,`get_all_substrings`函数接受一个字符串`s`和一个可选的起始位置参数`start`,默认值为0。如果`start`等于字符串长度,则返回空列表,否则遍历从起始位置开始的所有子串,并将它们添加到结果列表中。然后递归调用函数,将起始位置增加一位,继续遍历以当前起始位置开始的所有子串。最终返回结果列表。