如何查找字符串w中满足uuu为其子串的最长子串u？

问题核心 #

你需要找的是连续三次重复的子串u（即uuu是原串的子串），而常规后缀数组+LCP数组的方法只能找到出现至少三次的子串（这三次可以分散在原串任意位置），这就是你之前尝试失败的原因——没验证这三次重复是否是连续相邻的。

改进思路 #

我们可以基于后缀数组+LCP做针对性优化，也可以用更简单的前缀哈希方法快速验证，核心思路是：

• 从最大的可能长度l（即len(w)//3）开始往下遍历，找到第一个存在i使得w[i:i+l] == w[i+l:i+2l] == w[i+2l:i+3l]的l，对应的子串就是答案。
• 用前缀哈希或RMQ（区间最小值查询）优化子串相等的判断，避免暴力比对的O(n²)复杂度。

方法1：前缀哈希法（简单高效） #

通过预处理前缀哈希，我们可以O(1)计算任意子串的哈希值，快速判断三个子串是否相等：

def longest_uuu_substring(w):
    n = len(w)
    if n < 3:
        return ""
    
    # 预处理前缀哈希和幂次（用双哈希可进一步降低碰撞概率，此处简化为单哈希）
    base = 911382629
    mod = 10**18 + 3
    prefix_hash = [0]*(n+1)
    power = [1]*(n+1)
    for i in range(n):
        prefix_hash[i+1] = (prefix_hash[i] * base + ord(w[i])) % mod
        power[i+1] = (power[i] * base) % mod
    
    # 从最大可能的l开始遍历，找到即返回
    max_l = n // 3
    for l in range(max_l, 0, -1):
        for i in range(n - 3*l + 1):
            # 计算三个连续子串的哈希值
            hash1 = (prefix_hash[i+l] - prefix_hash[i] * power[l]) % mod
            hash2 = (prefix_hash[i+2*l] - prefix_hash[i+l] * power[l]) % mod
            hash3 = (prefix_hash[i+3*l] - prefix_hash[i+2*l] * power[l]) % mod
            if hash1 == hash2 == hash3:
                return w[i:i+l]
    return ""

方法2：后缀数组+LCP+RMQ优化 #

如果你坚持用后缀数组，需要先预处理LCP数组和RMQ结构，快速查询任意两个后缀的最长公共前缀长度：

1. 先生成后缀数组SA和LCP数组（可采用高效的SA-IS算法实现）
2. 构建RMQ结构（比如ST表），用于O(1)查询LCP数组的区间最小值（对应两个后缀的LCP长度）
3. 遍历每个可能的l，检查是否存在i，使得：
   • 后缀i和后缀i+l的LCP >= l（即w[i:i+l] == w[i+l:i+2l]）
   • 后缀i+l和后缀i+2l的LCP >= l（即w[i+l:i+2l] == w[i+2l:i+3l]）

示例代码框架（省略SA和ST表的底层实现，可自行补充高效实现）：

def build_sa(s):
    # 实现SA-IS算法生成后缀数组
    pass

def build_lcp(s, sa):
    n = len(s)
    rank = [0]*n
    for i in range(n):
        rank[sa[i]] = i
    k = 0
    lcp = [0]*(n-1)
    for i in range(n):
        if rank[i] == n-1:
            k = 0
            continue
        j = sa[rank[i]+1]
        while i+k < n and j+k < n and s[i+k] == s[j+k]:
            k += 1
        lcp[rank[i]] = k
        if k > 0:
            k -= 1
    return lcp

def build_st(lcp):
    # 构建ST表用于RMQ查询
    n = len(lcp)
    logn = n.bit_length()
    st = [[0]*n for _ in range(logn)]
    st[0] = lcp.copy()
    for k in range(1, logn):
        for i in range(n - (1<<k) + 1):
            st[k][i] = min(st[k-1][i], st[k-1][i + (1<<(k-1))])
    return st, logn

def query_lcp(st, logn, rank_a, rank_b):
    # 查询两个后缀的最长公共前缀长度
    if rank_a == rank_b:
        return len(w) - sa[rank_a]
    rank_a, rank_b = sorted((rank_a, rank_b))
    length = rank_b - rank_a
    k = length.bit_length() - 1
    return min(st[k][rank_a], st[k][rank_b - (1<<k) + 1])

def longest_uuu_substring_sa(w):
    n = len(w)
    if n < 3:
        return ""
    sa = build_sa(w)
    lcp = build_lcp(w, sa)
    st, logn = build_st(lcp)
    rank = [0]*n
    for i in range(n):
        rank[sa[i]] = i
    
    max_l = n//3
    for l in range(max_l, 0, -1):
        for i in range(n - 3*l + 1):
            # 验证连续三个子串是否相等
            lcp1 = query_lcp(st, logn, rank[i], rank[i+l])
            lcp2 = query_lcp(st, logn, rank[i+l], rank[i+2*l])
            if lcp1 >= l and lcp2 >= l:
                return w[i:i+l]
    return ""

关键说明 #

• 常规LCP找重复三次子串的逻辑，是找SA中连续三个后缀的LCP最小值>=l，这只能说明三个后缀的前l个字符相同，但无法保证它们的起始位置是i, i+l, i+2l，因此无法对应uuu的连续重复结构。
• 上面的方法针对性地验证了三个子串的起始位置是连续偏移l的，确保找到的是真正的uuu子串。

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