技术需求：查找大字符串中的连续重复子串（偏好线性时间解法）

给定一个字符串，需要找出其中所有连续重复的子串（可能存在多个）。由于字符串规模可能极大，必须采用线性时间复杂度的解决方案。最终输出每个重复模式的：

• 起始位置
• 结束位置
• 重复单元的大小

示例说明 #

对应输出逻辑 #

假设字符串由以下代码输出（部分打印语句在循环内）：

print('a')
print('x')
print('b')
print('r')
for _ in range(5):
    print('x')
    print('r')
    print('b')
print('m')
print('u')

生成的字符串 #

axbrxrbxrbxrbxrbxrbxrbmu

检测结果 #

Start: 4
End: 18
Size: 3

线性时间解决方案 #

采用KMP算法中的前缀函数实现O(n)时间复杂度的检测，具体步骤：

1. 计算字符串的前缀函数数组pi：pi[i]代表字符串前i+1个字符组成的子串中，最长相等前缀与后缀的长度。
2. 遍历数组，对每个位置i：
   • 计算当前子串长度curr_len = i + 1
   • 若curr_len % (curr_len - pi[i]) == 0，则重复单元长度为unit_size = curr_len - pi[i]
   • 进一步验证该区间是否为连续重复的完整范围，排除非连续的重复情况，确定起始和结束位置
3. 收集所有有效重复模式，去重后输出结果

核心优势 #

• 前缀函数计算和后续检测均为线性时间，完全适配大规模字符串场景
• 可处理嵌套重复模式，确保输出最长的连续重复区间，避免冗余记录

内容的提问来源于stack exchange，提问作者Branky