逐字符构造字符串相邻重复子串快速校验及性能优化咨询

需求说明 #

逐字符拼接构造字符串的过程中，每新增一个字符就校验当前字符串是否存在相邻重复子串，一旦检测到则判定为无效，不再继续拼接后续字符。

• 无效字符串示例：AA、ABAA、ABACAA、ABACABAC、ABACABAB
• 有效字符串示例：AB、ABC、ABA、ABACABADAB、ABACABCACBABCABACABCACBACAB

注：每次新增字符都会调用校验函数，因此类似ABABC这类字符串不会触发全量校验，拼接第二个B时字符串就已经被判为无效，终止后续流程。

现有实现代码 #

版本1 #

def is_valid(s):
    if len(s) < 2:
        return True

    # 校验最后两个字符是否相同
    if s[-1] == s[len(s)-2]:
        return False

    # 获取最后一个字符在之前字符串中出现的所有索引并倒序排列
    indexes = [m.start() for m in re.finditer(s[-1], s[:-1])]
    indexes = indexes[::-1]

    for index in indexes:
        a = s[index+1:]
        if index - len(a) + 1 < 0:
            return True
        b = s[index-len(a)+1 : index+1]
        if a == b: 
            return False

    return True

版本2 #

def is_valid(s):
    # 反转字符串
    s = s[::-1]

    substring = ""
    for i in range(len(s)):
        substring += s[i]

        if len(s) >= i+1+len(substring) and s[i+1 : i+1+len(substring)] == substring:
            return False

    return True

待解答问题 #

1. 现有Python实现是否有较大的性能优化空间？
2. 如果现有方案优化空间不大，改用C++/C#或者Java实现是否会有明显的性能提升？

问题1：Python实现的优化空间 #

现有两个版本存在非常大的性能优化空间，核心冗余点如下：

• 版本1引入正则匹配查询历史索引额外开销，且频繁生成字符串切片做对比，内存拷贝成本很高
• 版本2每次全量反转字符串、逐次拼接子串、切片对比的操作，最差时间复杂度为O(n²)，且Python不可变字符串的操作开销被进一步放大

优化方向 #

利用增量校验的特性：每次仅新增1个字符，可能存在的相邻重复子串一定是字符串的后缀对，仅需要校验长度为k的后缀和前面相邻的等长片段是否一致即可，k的取值范围仅为1到len(s)//2，不需要处理前缀无关内容。同时用下标直接对比代替切片拷贝，避免额外内存分配。

优化后实现 #

def is_valid(s: str) -> bool:
    n = len(s)
    if n < 2:
        return True
    max_k = n // 2
    # 从短到长校验后缀重复对，短重复出现概率更高，可以更快命中返回
    for k in range(1, max_k + 1):
        is_match = True
        for i in range(k):
            if s[n - 2*k + i] != s[n - k + i]:
                is_match = False
                break
        if is_match:
            return False
    return True

该实现相比原有版本性能可以提升3_{10倍，若需要进一步优化，可以将字符串提前转为字节数组做对比，减少Unicode字符解析开销，性能还能再提升1}2倍。

问题2：编译型语言的性能提升效果 #

如果优化后的Python版本仍无法满足性能要求，改用C++/C#/Java这类编译型语言会有10~50倍的明显性能提升，核心原因如下：

1. 没有Python的动态类型解析、GIL、字节码解释执行的额外开销
2. 字符串操作可以直接通过指针偏移、栈内存完成，不需要不可变对象的拷贝开销
3. 可以利用SIMD指令实现批量字符对比，极端场景下还能再获得数倍性能提升

如果需要兼顾开发效率和运行性能，也可以用C++实现核心校验逻辑，通过pybind11/ctypes给Python调用，是性价比很高的方案。

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