不使用正则表达式匹配字符串重复模式的问题及代码优化

需求明确：不能导入re模块、不能用正则表达式，要找出字符串里的重复模式。比如输入字符串AABACCCACCACCACCACCACC时，前缀是AAB，后面反复出现ACC，期望结果为AAB(ACC)。

用户自己编写了一段Python代码，但存在缺陷——处理字符串AAAAAAAAAAAAAAAAAABDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBD时，代码返回AA，但正确结果应该是AAAAAAAAAAAAAAAAAA(BD)。

用户的原代码如下：

def get_pattern(trail):
    for j in range(0,len(trail)):
        k = j+1
        while k<len(trail) and trail[j]!=trail[k]:
            k+=1
        if k==len(trail)-1:
            continue

        window = ''
        stop = trail[j]
        m = j
        while  m<len(trail) and k<len(trail) and trail[m]==trail[k]:
            window+=trail[m]
            m+=1
            k+=1
            if trail[m]==stop and len(window)>1: 
                break

        if len(window)>1:
            prefix=''
            if j>0:
                prefix = trail[0:j]
            return prefix+'('+window+')'
        
    return False

问题分析 #

原代码的核心问题在于：它一找到第一个短重复片段（比如开头的AA）就直接返回，完全没检查后面是否存在覆盖范围更大的有效重复模式；同时判断重复的逻辑不严谨，只匹配了一小段就认定是重复模式，没有验证后续所有内容是否都符合该模式。

正确实现方法 #

换个思路：从所有可能的前缀长度入手，逐个检查剩余字符串是否由某个模式重复构成，优先匹配能覆盖剩余全部内容的模式（即让前缀尽可能长）。

具体步骤：

1. 遍历所有可能的前缀长度，从0开始，直到字符串总长度的一半（剩余部分至少要能放下两个重复模式）。
2. 对每个前缀，取出剩余字符串，遍历所有可能的模式长度（从1到剩余长度的一半）。
3. 检查剩余字符串长度是否能被当前模式长度整除，且所有分段都和模式完全一致。
4. 一旦找到符合条件的模式，直接返回结果；遍历完所有可能都没找到，返回False。

正确代码：

def get_pattern(trail):
    total_len = len(trail)
    # 遍历所有可能的前缀长度，前缀可以为空（从0开始）
    for prefix_len in range(total_len):
        remaining = trail[prefix_len:]
        remaining_len = len(remaining)
        if remaining_len < 2:
            continue  # 至少需要重复两次，剩余长度不够直接跳过
        # 遍历可能的模式长度，最长不超过剩余长度的一半
        for pattern_len in range(1, remaining_len // 2 + 1):
            if remaining_len % pattern_len != 0:
                continue  # 长度不能整除，肯定不是重复模式
            pattern = remaining[:pattern_len]
            # 验证所有分段是否都等于当前模式
            is_valid = True
            for i in range(1, remaining_len // pattern_len):
                segment = remaining[i*pattern_len : (i+1)*pattern_len]
                if segment != pattern:
                    is_valid = False
                    break
            if is_valid:
                prefix = trail[:prefix_len]
                return f"{prefix}({pattern})"
    # 没有找到任何重复模式
    return False

测试验证 #

• 输入AABACCCACCACCACCACCACC，返回AAB(ACC)，符合预期。
• 输入AAAAAAAAAAAAAAAAAABDBDBDBDBDBDBDBDBDBDBDBDBDBDBDBD，返回AAAAAAAAAAAAAAAAAA(BD)，解决了原代码的问题。

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