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