如何从文本中查找长度超过6个字符的重复字符串？

需求与示例 #

• 目标：从文本里找出重复出现的连续长字符串，过滤掉过短的重复片段（比如示例中6字符的' text '不返回），预期返回'his is '
• 示例文本：

x = 'This is a sample text and this is lowercase text that is repeated.'

你尝试的代码 #

import re
from collections import Counter

duplist = list()
for i in range(1, 30):
  mylist = re.findall('.{1,'+str(i)+'}', x)
  duplist.append([k for k,v in Counter(mylist).items() if v>1])

现有代码的问题 #

这段代码会生成所有长度1到29的子串并统计重复，但存在两个核心问题：

1. 会返回大量短重复子串，无法自动筛选出符合要求的长片段
2. 用re.findall生成的子串包含大量重叠内容，效率很低，还容易截断有效重复片段

改进方案 #

思路 #

从最长可能的子串长度开始倒序查找，找到第一个重复的长片段就返回，同时设置最小长度过滤短子串，既保证结果符合预期，又提升效率。

改进后的代码 #

def find_longest_duplicate_substring(s, min_length=7):
    # 最长可能的重复子串长度不超过文本长度的一半
    max_possible_len = len(s) // 2
    # 从最长到最短遍历子串长度
    for length in range(max_possible_len, min_length - 1, -1):
        substr_map = {}
        # 滑动窗口生成所有当前长度的子串
        for start in range(len(s) - length + 1):
            substr = s[start:start+length]
            if substr in substr_map:
                return substr
            substr_map[substr] = 1
    # 没找到符合条件的子串时返回None
    return None

# 测试示例
x = 'This is a sample text and this is lowercase text that is repeated.'
target_substr = find_longest_duplicate_substring(x, min_length=7)
print(target_substr)  # 输出: his is 

代码说明 #

• 倒序遍历子串长度，确保找到的第一个重复子串就是最长的
• min_length参数可以灵活调整，比如设为7就会排除6字符及以下的重复片段
• 滑动窗口生成子串，避免了冗余的重叠内容，比正则的方式更高效

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