问题分析

我们需要将目标01串 $S$ 划分为若干子串，每个子串必须是某个模式串的前缀或后缀，目标是找到划分方案使得模式串费用之和最小。

关键难点：

• 模式串数量 $n$ 和总长度 $L$ 都可达 $3\times 10^5$
• 每个子串可以是任意模式串的任意前缀或后缀
• 需要高效处理大量字符串匹配和动态规划转移

算法思路

1. 核心数据结构：双Trie树

建立两个Trie树：

• 正向Trie ($tl$)：存储所有模式串，用于处理"前缀"匹配
• 反向Trie ($tr$)：存储所有模式串的反转，用于处理"后缀"匹配

每个Trie节点维护：

• 到达该节点的最小费用 $w[x]$
• 树链剖分信息（重儿子、DFS序等）
• 哈希值用于快速字符串匹配

2. 动态规划框架

定义 $f[i]$ 表示将 $S$ 的前 $i$ 个字符划分的最小费用。

状态转移：

• 从位置 $i$ 开始，找到所有可能的匹配长度 $len$
• $f[i+len] = \min(f[i+len], f[i] + cost)$

3. 高效匹配算法

Trie树上的快速查询

• 使用树链剖分优化Trie树上的遍历
• 利用字符串哈希快速比较路径匹配长度
• 通过二分查找确定最长匹配前缀

优化转移更新

对于每个匹配位置，采用两种策略：

1. 短链暴力更新（长度 ≤ $K=10$）：

   • 直接枚举所有可能的长度进行转移

2. 长链数据结构优化：

   • 使用树状数组维护区间最小值
   • cl：处理正向匹配的延迟更新
   • cr：处理反向匹配的快速查询

4. 算法流程

1. 预处理阶段：

   • 构建正向和反向Trie树
   • 进行树链剖分和哈希计算
   • 初始化动态规划数组

2. 主循环：

   • 对于每个位置 $i$，更新树状数组
   • 查询从 $i$ 开始的所有正向匹配
   • 查询以 $i$ 结尾的所有反向匹配
   • 更新动态规划状态

复杂度分析

• Trie构建：$O(L)$
• 树链剖分：$O(L)$
• 动态规划：$O(m \times K + m \log m)$
• 总复杂度：$O(m \times K + L)$，其中 $K=10$ 为短链阈值

算法优势

1. 双Trie设计：巧妙处理前缀和后缀两种匹配条件
2. 树链剖分+哈希：将字符串匹配转化为树上的高效操作
3. 混合更新策略：结合暴力枚举和数据结构，平衡常数因子
4. 空间优化：重复利用Trie结构，控制内存使用

总结

本题的解法展示了如何将复杂的字符串划分问题转化为Trie树上的动态规划问题。通过精心设计的数据结构和优化策略，算法在 $O(n)$ 级别的时间内解决了大规模实例。

核心技术点：

• 双Trie处理前后缀匹配
• 树链剖分加速Trie遍历
• 字符串哈希快速比较
• 混合更新策略平衡效率