面试技术题：判断给定字符串是否含连续重复子串及解法疑问

问题明确 #

面试题要求：判断给定字符串是否包含紧接着自身重复出现的子串。示例：

• ATAYTAYUV → 包含连续重复的TAY（TAY紧接着TAY）
• AABCD → 包含连续重复的A（A紧接着A）
• ABCAB → 两个AB不连续，返回否

你的思路分析 #

你的思路有一定合理性，但存在明显局限性：

• 仅从第一个字符的第二次出现位置开始匹配，会漏掉重复子串不是从字符串首字符开始的情况。比如字符串XABABY，首字符X没有第二次出现，按你的思路会直接返回否，但实际存在连续重复的AB。
• 当匹配失败后从最后检查位置重新开始的逻辑，也可能跳过潜在的重复子串起点，无法覆盖所有可能的情况。

可行解法汇总 #

1. 暴力遍历（简单直观）

遍历所有可能的重复子串长度l（范围1到len(s)//2，因为重复两次至少需要2l长度），对每个长度l，检查字符串中是否存在位置i，使得s[i:i+l]与s[i+l:i+2l]完全相等。只要找到任意一个满足的情况，就返回True，否则返回False。

Python示例代码：

def has_consecutive_duplicate(s):
    n = len(s)
    max_sub_len = n // 2
    for sub_len in range(1, max_sub_len + 1):
        # 遍历所有可能的起始位置，确保后续有足够长度容纳两个子串
        for start in range(n - 2 * sub_len + 1):
            if s[start:start+sub_len] == s[start+sub_len:start+2*sub_len]:
                return True
    return False

该方法时间复杂度为O(n²)，适合短字符串场景，逻辑简单易实现。

2. KMP前缀函数优化（最优时间复杂度）

利用KMP算法的前缀函数（pi数组）可以在O(n)时间内完成判断。前缀函数数组pi[i]表示字符串s[0..i]中最长相等前缀和后缀的长度。如果存在连续重复子串，必然满足：

• 某个位置i的pi[i] != 0
• (i+1)能被(i+1 - pi[i])整除（即子串长度是重复单元的整数倍）
• pi[i] >= (i+1 - pi[i])（确保存在至少两次连续重复）

Python示例代码：

def has_consecutive_duplicate(s):
    n = len(s)
    pi = [0] * n
    for i in range(1, n):
        j = pi[i-1]
        while j > 0 and s[i] != s[j]:
            j = pi[j-1]
        if s[i] == s[j]:
            j += 1
        pi[i] = j
        # 检查是否存在连续重复子串
        unit_len = i + 1 - pi[i]
        if pi[i] != 0 and (i+1) % unit_len == 0 and pi[i] >= unit_len:
            return True
    return False

该方法时间复杂度为O(n)，是处理长字符串的最优解法。

总结 #

你的思路可以作为特定场景下的尝试，但无法覆盖所有情况。面试中如果提出这个思路，需要主动说明其局限性，同时补充更全面的解法，能体现你对问题的深入思考。

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