Hackerrank超级函数字符串(Super-Functional Strings)超时问题优化咨询

你的原代码超时主要是因为子串生成与重复检查的效率极低：每次生成子串需要O(k)时间（k为子串长度），且用列表的in操作做重复检查是O(m)时间（m为已存储子串数量），整体复杂度达到O(n³)，对于较长字符串必然超时。下面给出两种优化方案，分别适合中小规模和大规模字符串场景。

方案一：滚动哈希+集合去重（中小规模字符串） #

这个方案通过滚动哈希快速计算子串哈希值，用集合做O(1)平均时间的重复检查，同时实时维护子串的不同字符数，避免了低效的子串生成和重复判断。

def superFunctionalStrings(s):
    MOD = 10**9 + 7
    MOD_HASH = 10**9 + 9  # 用不同大质数降低哈希冲突概率
    BASE = 911382629       # 哈希基数
    n = len(s)
    total = 0
    hash_set = set()
    
    for i in range(n):
        seen = [False] * 26
        distinct = 0
        current_hash = 0
        for j in range(i, n):
            c = ord(s[j]) - ord('a')
            # 更新当前子串的不同字符数
            if not seen[c]:
                seen[c] = True
                distinct += 1
            # 滚动计算子串哈希值，避免生成完整子串
            current_hash = (current_hash * BASE + (c + 1)) % MOD_HASH
            # 检查是否为新子串
            if current_hash not in hash_set:
                hash_set.add(current_hash)
                length = j - i + 1
                # 高效计算length^distinct mod MOD
                term = pow(length, distinct, MOD)
                total = (total + term) % MOD
    return total

优化亮点： #

1. 滚动哈希：无需生成完整子串，O(1)时间计算子串哈希值。
2. 集合去重：用set存储哈希值，平均O(1)完成重复检查，远快于列表的O(m)查找。
3. 实时维护不同字符数：对每个起始位置i，遍历j时用数组seen记录已出现字符，O(1)更新不同字符数。

方案二：后缀自动机（SAM）高效解法（大规模字符串） #

对于长度超过1000的字符串，O(n²)方案仍可能超时，此时可以用后缀自动机（SAM），它能在O(n)时间内构建，线性遍历所有不同子串，将时间复杂度优化到O(n*26)。

def superFunctionalStrings(s):
    MOD = 10**9 + 7
    n = len(s)
    if n == 0:
        return 0
    
    # 预处理前缀字符计数：pre[i][c]表示前i个字符中字符c的出现次数
    pre = [[0]*26 for _ in range(n+1)]
    for i in range(n):
        c = ord(s[i]) - ord('a')
        pre[i+1] = pre[i].copy()
        pre[i+1][c] += 1
    
    # SAM状态类
    class State:
        def __init__(self):
            self.len = 0          # 状态对应最长子串长度
            self.link = -1        # 后缀链接
            self.next = [-1]*26   # 字符转移
            self.end_pos = -1     # 记录子串的一个结束位置
    
    size = 1
    last = 0
    states = [State()]
    
    # 构建后缀自动机
    for i in range(n):
        c = ord(s[i]) - ord('a')
        p = last
        curr = size
        size += 1
        states.append(State())
        states[curr].len = states[p].len + 1
        states[curr].end_pos = i
        
        while p != -1 and states[p].next[c] == -1:
            states[p].next[c] = curr
            p = states[p].link
        
        if p == -1:
            states[curr].link = 0
        else:
            q = states[p].next[c]
            if states[p].len + 1 == states[q].len:
                states[curr].link = q
            else:
                clone = size
                size += 1
                states.append(State())
                states[clone].len = states[p].len + 1
                states[clone].next = states[q].next.copy()
                states[clone].link = states[q].link
                states[clone].end_pos = states[q].end_pos
                
                while p != -1 and states[p].next[c] == q:
                    states[p].next[c] = clone
                    p = states[p].link
                states[q].link = clone
                states[curr].link = clone
        last = curr
    
    total = 0
    # 遍历所有状态（跳过初始状态0）
    for u in range(1, size):
        state = states[u]
        link_state = states[state.link]
        min_len = link_state.len + 1
        max_len = state.len
        end_pos = state.end_pos
        
        # 计算该状态下所有不同子串的贡献
        for k in range(min_len, max_len + 1):
            start_pos = end_pos - k + 1
            # 统计子串的不同字符数
            distinct = 0
            for c in range(26):
                if pre[end_pos+1][c] - pre[start_pos][c] > 0:
                    distinct += 1
            term = pow(k, distinct, MOD)
            total = (total + term) % MOD
    
    return total

优化亮点： #

1. 线性构建SAM：SAM的状态数为O(n)，构建过程均摊O(n)时间。
2. 无重复遍历子串：每个状态对应一组唯一的子串，避免了重复处理相同子串。
3. 前缀和快速统计字符数：预处理前缀和数组后，每个子串的不同字符数可在O(26)时间内统计。

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