1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| \section{错误三：BFS 建自动机时 \texttt{nxt} 表不完整}
\subsection*{错误代码}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
auto v = u.next_state(i);
if (mp.contains(v)) {
continue; // 错误：跳过了，但没有记录转移边
}
mp[v] = idx;
nxt[mp[u]][i] = idx;
++idx;
q.push(v);
}
\end{minted}
\subsection*{错误分析}
当目标状态 \texttt{v} 已经在 BFS 中被访问过时，代码直接 \texttt{continue}，\textbf{没有设置 \texttt{nxt[mp[u]][i] = mp[v]}}。这导致所有"转移到已访问状态"的边全部留为初始值 $-1$。
自动机共 $40$ 个状态、$80$ 条有向边，但其中只有 $39$ 条（BFS 树边）被正确记录，剩下 $41$ 条（回边和交叉边）全部丢失。后续的子序列 DP 在遇到这些 $-1$ 的转移时会直接跳过，导致大量合法的子序列转移被忽略。
\subsection*{修复}
\begin{minted}{cpp}
for (int i = 0; i < 2; ++i) {
auto v = u.next_state(i);
if (mp.contains(v)) {
nxt[mp[u]][i] = mp[v];
continue;
}
mp[v] = idx;
idx_state[idx] = v;
nxt[mp[u]][i] = idx;
++idx;
q.push(v);
}
\end{minted}
\subsection*{教训}
BFS 建图时，"发现新节点"和"记录边"是两个独立的操作。即使目标节点已经在队列中，从当前节点到它的\textbf{转移边}仍然必须被记录。这是 BFS 建自动机的经典易错点。
|
