警示后人,如果你WA80
查看原帖
警示后人,如果你WA80
1088873
Tanliu楼主2025/1/23 22:57

在判断一个AC自动机上的节点是否合法,也就是这个节点是否有一个后缀是一个单词的时候,不能只判断这个点是否是一个完整单词、这个点的fail是否是一个完整单词。因为有可能这个点的fail的fail是一个完整单词(大概也就只有我这么糖的人会错这了)。

所以应该在get_fail时判断fail节点是否是不合法的,如果是就标记,因为get_fail时是bfs遍历,所以一定不会有遗漏。

wwww……,模拟赛丢了20分

2025/1/23 22:57
加载中...