有限状态机 · 在位流里命中「1011」

每送一位走一步状态 · 命中点灯 · 失配不回零
这一关变了:输入不再是「要输出的内容」,而是「考验状态机的考题」。 状态机每读一位就走一步,只有完整走过目标模式的那几步才点一次灯 —— 它是真正的「有记忆的逻辑」: 输出不再只看当前输入,还看走过的路。
怎么玩:目标是让脉冲输出恰好点亮 3 次。点 0 / 1 逐位喂入, 或把整段位流粘进输入框一次发送,Backspace 撤销一位,R 重置。
反直觉一:失配不回零。比如已匹配「101」再读到 0,状态机不会从头再来, 而是回退到「最长真前后缀」继续 —— 已匹配的「10」依然算数。这正是 KMP 算法在硬件里的样子。 反直觉二:重叠命中。目标 1011 时,输入 1011011 会命中 2 次 —— 两次命中共享中间那个 1。 所以「多送一位」和「少送一位」一样致命:多送的位可能拼出第 4 次命中,也可能恰好不够。 反直觉三:状态数与模式长度同阶。不管你喂多长的位流,状态机只用 m+1 个状态就记住了整个模式 —— 这就是它比「存下整段位流再找」省得多的原因。
展开:状态转移表与失配回退(fail 数组)