不使用numpy/pypy/cython，如何加速Python循环？USACO题目超时求助

你的代码超时的核心原因是时间复杂度远高于O(n)：

• 每次调用s.index(c)需要遍历字符串查找子串，时间复杂度为O(n)
• 字符串拼接s[:i] + s[i + l:]会创建新字符串，同样是O(n)时间开销
• 最坏情况下（比如输入字符串是连续重复的字符，审查串是两个相同字符），这个循环会重复O(n)次，整体时间复杂度退化为O(n²)，面对大测试用例必然超时

优化解法：栈结构实现线性时间复杂度 #

使用栈可以在遍历原字符串的同时，实时维护当前匹配审查串的进度，确保整体时间复杂度为O(n)：

with open('censor.in', 'r') as f:
    s = f.readline().strip()
    c = f.readline().strip()

c_len = len(c)
stack = []
match_progress = []  # 记录栈中每个位置对应的审查串匹配长度

for char in s:
    stack.append(char)
    # 计算当前字符的匹配进度
    if match_progress and char == c[match_progress[-1]]:
        current_progress = match_progress[-1] + 1
    else:
        current_progress = 1 if char == c[0] else 0
    match_progress.append(current_progress)
    
    # 匹配完成则移除对应长度的栈元素
    if current_progress == c_len:
        del stack[-c_len:]
        del match_progress[-c_len:]

result = ''.join(stack)

with open('censor.out', 'w') as f:
    f.write(result)

或者更简化的写法，直接在栈中存储字符和匹配进度的元组：

with open('censor.in', 'r') as f:
    s = f.readline().strip()
    c = f.readline().strip()

c_len = len(c)
stack = []

for char in s:
    # 初始匹配进度：如果当前字符是审查串首字符则为1，否则0
    progress = 1 if char == c[0] else 0
    # 检查是否能延续上一个位置的匹配
    if stack and char == c[stack[-1][1]]:
        progress = stack[-1][1] + 1
    stack.append( (char, progress) )
    
    # 匹配完成则弹出对应长度的元素
    if progress == c_len:
        del stack[-c_len:]

result = ''.join([char for char, _ in stack])

with open('censor.out', 'w') as f:
    f.write(result)

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