好题

观察这道题，发现有关字串的题目，一般来说，这种题都要构建\(AC\)自动机，所以考虑构建。

构建之后，原来的所有 \(fail\) 是一个树形结构。

解法 \(1\):

考虑从询问入手，那么对于每一个询问，等价于就是查询每一个 \(Q_i\) 包含的后缀的最大值，再对这些最大值取 \(max\)，那么 \(Q\) 在跳 \(fail\) 树时，查询所有 \(Q_i\) 点到根的最大值，再将这些最大值取 \(max\)，就是答案，考虑：树剖 \(+\) 单点修改。

时间复杂度 \(O(n~log^2~n)\)

解法 \(2\)：

考虑从修改入手，那么对于修改字符串 \(s\)，代表字符串 \(s\) 的点的整个子树的最大值都会受到影响，修改整个子树内的每个点的最大值，查询 \(Q\) 时，让 \(Q\) 在跳 \(fail\) 树时对于每一个 \(Q_i\) 的值取一个 \(max\)，那么考虑：子树修改 \(+\) 单点查询

注意：用 \(multiset\)(可重并查集，且自动排序) 去维护

时间复杂度 \(O(n~log^2~n)\)，因为有些东西并不是 \(O(1)\) 的

解法 \(3\)：