### Python 实现检测字符串中重复子串并统计重复次数的算法 为了实现一个能够检测输入字符串中的重复子串及其出现次数的功能，可以采用滑动窗口技术和哈希表相结合的方式。这种方法的核心在于通过逐步扩展子串长度，并将其存储到字典中以便后续查询。 以下是基于 Python 的一种实现方式： #### 算法思路 1. 定义一个空字典用于保存所有可能的子串及其对应的出现次数。 2. 使用两层循环遍历所有的子串可能性：外层控制起始位置，内层控制结束位置。 3. 对于每一个子串，更新其在字典中的计数值。 4. 遍历结束后，筛选出那些出现次数大于 1 的子串作为最终结果返回。 #### 示例代码 ```python def find_duplicate_substrings(s): substring_count = {} n = len(s) for start in range(n): for end in range(start + 1, n + 1): substr = s[start:end] if substr in substring_count: substring_count[substr] += 1 else: substring_count[substr] = 1 # 过滤掉只出现一次的子串 duplicates = {key: value for key, value in substring_count.items() if value > 1 and len(key) > 1} return duplicates # 测试用例 if __name__ == "__main__": test_string = "banana" result = find_duplicate_substrings(test_string) print("重复子串及出现次数:") for substr, count in result.items(): print(f"子串: \"{substr}\", 出现次数: {count}") ``` #### 结果解释 当运行上述程序时，对于测试字符串 `"banana"`，输出将是： ``` 重复子串及出现次数: 子串: "an", 出现次数: 2 子串: "na", 出现次数: 2 子串: "ana", 出现次数: 2 ``` 此方法利用双重循环枚举所有可能的子串，并借助字典记录每种子串的频率[^7]。 --- ### 性能优化建议 尽管上述方法简单易懂，但在面对较长字符串时效率较低。因此可考虑以下两种更高效的替代方案： 1. **Rabin-Karp 字符串匹配算法**：通过预计算哈希值来加速子串比较过程，从而显著降低时间复杂度[^8]。 2. **后缀数组或后缀自动机(SAM)**：这两种高级数据结构特别适合处理涉及大量重复模式的大规模文本分析任务[^9]。 ---