构建最短母串的 AC 自动机算法详解

根据题意，我们需要构造一个最短的母串 S。具体的做法是，首先将所有的字符串加入到一棵 Trie 树中，并在每个子串的末尾节点打上一个标记，表示这个节点被哪些字符串经过。然后，我们通过运行 AC 自动机来构建 fail 指针（fail 树）。对于一个节点 x，它需要从它 fail 树上的父节点那里转移标记，这样就可以找出到达某个节点时所出现的新字符串。接下来，我们使用 BFS 来寻找最短母串。

我们可以定义一个二维数组 vis[u][state]，其中 vis[u][state] 表示是否在匹配状态为 state 时经过节点 u。当我们找到一个节点满足它的状态等于最终状态时，输出它走过的路径长度，即为答案。

具体的实现步骤如下：

首先，我们需要构建 Trie 树。将所有的字符串加入到 Trie 树中，并在每个子串的末尾节点打上标记。
然后，我们需要构建 AC 自动机。通过遍历 Trie 树的每个节点，并使用 BFS 来构建 fail 指针。

2.1 首先，将根节点入队，并将其 fail 指针指向自己。

2.2 使用 BFS 的方式遍历队列中的节点，直到队列为空。

2.3 对于当前节点 cur，遍历其所有的子节点 next。
```
2.3.1 如果 cur 的 fail 指针为根节点或者 cur 的子节点为空，则将 next 的 fail 指针指向根节点。

2.3.2 否则，将 cur 的 fail 指针的子节点指向 next，并将 next 的 fail 指针指向 cur 的 fail 指针的子节点。
```
使用 BFS 来寻找最短母串。

3.1 首先，将根节点入队，并将其状态初始化为 0。

3.2 使用 BFS 的方式遍历队列中的节点，直到队列为空。

3.3 对于当前节点 cur，遍历其所有的子节点 next。
```
3.3.1 如果 next 的状态等于最终状态，则输出 cur 的路径长度，即为答案。

3.3.2 否则，将 next 的状态更新为 cur 的状态与 next 的标记的按位或。
```
3.4 如果没有找到满足条件的节点，则输出不存在。

通过上述的步骤，我们可以构造出一个最短的母串 S，并输出其长度作为答案。