题解

问题分析

题目要求计算多个字符串的所有前缀子串的 ( h ) 函数值，其中 ( h(S) ) 定义为子串 ( S[l:r] ) 的平均权值 ( \frac{g(S[l:r])}{r-l+1} ) 的最大值，( g ) 函数是子串中所有模式串出现次数与对应权值的乘积和。

关键挑战：

1. 高效计算所有子串的 ( g ) 值（需快速匹配多个模式串）。
2. 对每个前缀子串，快速找到使平均权值最大的子区间（涉及分数最大值求解）。

核心思路

1. AC自动机构建：

   • 对所有模式串构建AC自动机（ac），用于正向匹配，快速计算子串中模式串的出现次数及权值和。
   • 对所有模式串的反转串构建另一个AC自动机（rev），用于反向匹配，辅助计算子串的权值和。

2. 权值预处理：

   • 在AC自动机中，通过fail指针（失配函数）传递权值，计算每个节点的累计权值w和前缀和sw，方便快速获取任意子串的g值。

3. 最大平均权值求解：

   • 对于每个前缀子串，使用单调队列（维护凸包）动态维护可能的最优子区间。通过分数比较（避免浮点数精度问题，使用__int128比较分子分母乘积），高效找到最大平均权值。
   • 利用tr数组关联正向和反向AC自动机的状态，快速获取子串的权值信息。

4. 结果整合：

   • 对每个前缀子串的最大平均权值进行传递和更新（结合AC自动机的fail和父节点信息），确保覆盖所有可能的子区间。
   • 根据测试类型（T=0或T=1）输出结果：T=0输出浮点数，T=1输出所有结果的异或和（模998244353）。

代码解析

1. AC自动机实现：

   • insert方法：插入字符串并构建Trie树，记录每个字符串的结束节点。
   • build方法：构建fail指针，通过BFS传播权值，计算w（节点累计权值）和sw（前缀累计权值）。

2. 分数处理：

   • frac结构体：存储分数a/b，实现分数比较（用__int128避免溢出）、转换为浮点数和模逆元的功能。

3. 单调队列（凸包维护）：

   • DS命名空间：维护动态添加的点，通过单调队列保证队列内点构成的线段斜率单调，高效查询最大平均权值（即最优子区间）。

4. 主逻辑：

   • 预处理正向和反向AC自动机，关联两者状态（tr数组）。
   • 对每个字符串的每个前缀，通过AC自动机跟踪状态，利用单调队列计算最大平均权值，更新f数组。
   • 传播最优值（结合fail和父节点），最终按测试类型输出结果。

总结

该解法通过AC自动机高效处理多模式串匹配，结合单调队列维护凸包解决最大平均权值问题，时间复杂度与总字符串长度线性相关，适用于大规模数据（( m \le 5 \times 10^6 )）。核心是利用自动机快速获取权值信息，并用几何方法（凸包）优化最大分数的查询。