题意概括

给定一个模板串 $t$，以及 $n$ 个字符串 $s_1, s_2, \dots, s_n$，保证每个 $s_i$ 都是 $t$ 的子串。
Alice 和 Bob 轮流操作，每次选择一个 $s_i$，在其末尾添加一个字符，使得新字符串仍然是 $t$ 的子串。
无法操作者输。双方都采取最优策略。问先手（Alice）是否必胜。

---

关键观察

这是一个 组合游戏，可以看成 $n$ 个独立的子游戏（每个 $s_i$ 对应一个游戏），每次操作时玩家选择其中一个游戏进行移动。根据 Sprague-Grundy 定理，整个游戏的胜负由每个子游戏的 SG 值的 XOR（异或）决定：若 XOR 不为 0，先手胜；否则后手胜。

因此问题转化为：对每个初始字符串 $s_i$，计算它的 SG 值。

---

如何定义单个子游戏

对一个固定字符串 $s$（它是 $t$ 的子串），操作是：在 $s$ 末尾加一个字符 $c$，使得 $s + c$ 仍是 $t$ 的子串。
如果不能再加任何字符（即没有合法的 $c$），则当前玩家输。

这可以建模为一个 有向图游戏：
状态 = 当前字符串 $s$。
从状态 $s$ 可以转移到 $sc$（其中 $c$ 是某个字符，且 $sc$ 是 $t$ 的子串）。

由于 $t$ 的长度有限，状态空间是有限的。

---

状态过多问题

如果直接以所有子串为状态，状态数最多是 $O(|t|^2)$，太大（$|t| \le 10^5$）。

我们需要更紧凑的表示。

---

思路：用后缀自动机（SAM）压缩状态

对于模板串 $t$，构建它的 后缀自动机（SAM）。

SAM 的每个结点（状态）表示 $t$ 的若干个子串（这些子串的 endpos 集合相同），并且这些子串的长度连续。

在 SAM 上，从初始状态（空串）开始，沿着转移边读字符，可以到达某个状态，表示当前字符串是该状态所表示的子串之一。

关键：当我们考虑在字符串 $s$ 末尾加字符时：

• 如果 $s$ 对应 SAM 上某个状态 $u$，那么加字符 $c$ 合法当且仅当在 SAM 上存在 $u \xrightarrow{c} v$。
• 新字符串 $sc$ 对应状态 $v$。

因此，我们可以将 SAM 的每个状态看作一个游戏状态。

---

SG 值的计算

定义 $sg(u)$ 表示当前字符串对应 SAM 状态 $u$ 时的 SG 值。

转移：

$$sg(u) = \text{mex}\{ sg(v) \mid u \xrightarrow{c} v \text{ 存在} \}. $$

其中 mex 表示最小的未出现在集合中的非负整数。

如果 $u$ 没有出边，则 $sg(u) = 0$（无法操作，当前玩家输）。

注意：同一个状态 $u$ 内可能对应多个不同长度的字符串，但它们后续能转移到的状态集合是一样的（因为转移只依赖于当前字符串所在状态，不依赖具体长度）。所以一个状态一个 SG 值是合理的。

---

多个初始字符串

给定初始字符串 $s_i$，我们可以在 SAM 上匹配，找到它对应的状态 $u_i$，然后它的 SG 值就是 $sg(u_i)$。

总游戏的 SG 值 = $sg(u_1) \oplus sg(u_2) \oplus \dots \oplus sg(u_n)$。

若不为 0，Alice 胜；否则 Bob 胜。

---

具体算法步骤

1. 对模板串 $t$ 建立 SAM。
2. 在 SAM 上拓扑排序（按 len 从大到小，或按 parent 树 BFS 逆序），计算每个状态的 SG 值：
   • 收集所有出边到达的状态的 SG 值。
   • 计算 mex。
3. 对每个初始串 $s_i$，在 SAM 上运行匹配，找到它最后停留的状态 $u_i$。
4. 计算 $X = sg(u_1) \oplus \dots \oplus sg(u_n)$，判断是否非零。

---

样例分析

样例 1

$t = \texttt{aaaa}$，SAM 状态：

• 状态 0（空串）：出边只有 $\texttt{a}$ 到状态 1。
• 状态 1（串 "a"）：出边 $\texttt{a}$ 到状态 2（"aa"）。
• 状态 2（"aa"）：出边 $\texttt{a}$ 到状态 3（"aaa"）。
• 状态 3（"aaa"）：出边 $\texttt{a}$ 到状态 4（"aaaa"）。
• 状态 4（"aaaa"）：无出边。

计算 SG：

• $sg(4) = 0$。
• $sg(3) = \text{mex}\{sg(4)\} = \text{mex}\{0\} = 1$。
• $sg(2) = \text{mex}\{sg(3)\} = \text{mex}\{1\} = 0$。
• $sg(1) = \text{mex}\{sg(2)\} = \text{mex}\{0\} = 1$。
• $sg(0) = \text{mex}\{sg(1)\} = \text{mex}\{1\} = 0$。

初始 $s = \texttt{a}$ 对应状态 1，SG = 1，总 SG = 1，非零，Alice 胜。

---

样例 2

$t = \texttt{abcabd}$。

SAM 比较复杂，但匹配 $s = \texttt{a}$：

• 状态 0 走 $\texttt{a}$ 到状态 $u$（对应 "a"），出边有 $\texttt{b}$（到 "ab"）等，至少一个出边，SG 不为 0。 但最终计算总 SG = $sg(u)$，需要具体计算 SAM。

简单验证：$s = \texttt{a}$ 可以加字符变成 "ab"，"ac" 不行（因为 "ac" 不是子串）。只有一个合法出边 "b" 到状态 $v$，$v$ 可能没有出边（"ab" 不能再加字符？在 $t$ 中 "ab" 后可以加 "c" 得 "abc"，是子串，所以有出边）。

实际上需要完整建 SAM 算 SG。样例输出 Bob，说明总 SG = 0，即 $sg(u) = 0$，说明从 "a" 出发所有后继状态的 SG 值集合包含 0，且 mex 得到 0。

---

复杂度分析

• 建 SAM：$O(|t|)$。
• 计算 SG：状态数 $O(|t|)$，每个状态出边最多字符集大小（常数 26），总 $O(|t|)$。
• 处理所有 $s_i$ 总匹配：$O(\sum |s_i|)$，题目保证总长 $\le 3\times 10^7$，可接受。

---

实现细节

1. SAM 构造：标准算法，每个状态记录转移 next[c]。
2. SG 计算：按 len 从大到小排序状态（因为 parent 树中父状态 len 小，但 SG 计算不依赖父子，只依赖转移边，所以可以任意顺序，但最好逆拓扑序保证后继先算）。
3. 匹配 $s_i$：从初始状态开始，依次读字符走转移，如果中途无转移，说明 $s_i$ 不是子串（但题目保证是子串，所以不会发生）。

---

总结

本题核心：

1. 将字符串添加字符游戏转化为 DAG 上的组合游戏。
2. 利用 SAM 压缩状态，将子串映射到状态。
3. 计算每个状态的 SG 值。
4. 多个初始串的 SG 异或判断胜负。

这样就能高效解决 $|t|$ 很大、$n$ 较小但总 $s_i$ 长度很大的情况。