「ROI 2019 Day2」模式串查找 (口胡)

设 \(S=\sum |w_i|\)

显然我们需要一个树形数据结构来维护题目中添加字符的操作

归纳一下，需要实现的操作就是：

1.添加一个新串

2.在当前串中分裂一段区间 \([L,R]\)

3.将一个串复制 \(k\) 次

将每一个单字符视为一个节点，考虑用一个可持久化的平衡树来维护上述操作，比如可持久化非旋 \(\text{Treap}\)

题解中给出的2-3-Tree不知道效果怎么样

2,3操作增加的数量为 \(\log\) 级别，最终的节点总数为 \(O(S+n\log S)\)

接下来需要实现的操作是合并两个子串的信息，显然在合并时计算跨过两个节点的串匹配模板串的次数

容易想到记录后缀匹配的 \(kmp\) 指针，但是这样的指针难以完成合并操作

为了计算这个，我们需要维护这个串的前缀/后缀 在 原串上最长的匹配子段

此时一个节点的信息可以用 \((l1,r1),(l2,r2),k\) 来表示，其中 \(k\) 标记了这个串是否整个出现在模板串中

合并子串 \(A,B\) 信息：

1.求出前缀/后缀匹配，以前缀为例：

1-1.如果 \(A\) 无法完全匹配，则匹配前缀为 \(A\) 的匹配前缀

1-2. \(A\) 能够完全匹配，设 \(A\) 在原串对应 \(L,R\) ， \(B\) 的最长匹配前缀在模板串匹配起始位置为 \(P\)

我们需要在 \([L,R]\) 之后借上 \(P\) 开始的一段后缀，而 \([L,R]\) 出现在模板串中的位置对应着后缀数组上一段 \(rank\) 区间

取模板串反向后缀数组，求出与 \(R\) 匹配长度超过 \(R-L+1\) 的 \(rank\) 区间 \([l,r]\)

则我们需要找到 \([l,r]\) 中 \(sa[i]+1\) 与 \(P\) 最长的 \(LCP\) ，显然是一个求临近 \(rank\) 的问题，可以在线主席树二分解决

由此得到最长前缀为 \(A\) 串再加上额外匹配得到的部分

\(O(\log m)\) 完成

\[ \ \]

2.求出跨过两个串的完美匹配个数

容易得到前串后缀对应的 \(\text{kmp}\) 指针，后串前缀对应反向的 \(\text{kmp}\) 指针

实际上就是求出这两个指针不断失配时相加恰好完全匹配的个数

注意到，实际上这个询问是完全可以离线的

可以通过在线得到的匹配情况，离线得到询问得到询问答案，再从叶子开始重新计算每个节点的答案

比较暴力的做法是：

建立两棵 \(\text{kmp}\) 树，在第一棵树上 \(\text{dfs}\) ，加入祖先对应的位置，然后再第二棵树上查询祖先匹配的个数

可以用 \(\text{dfs}\) 序+差分树状数组维护，复杂度为 \(O(\log m)\)

\[ \ \]

因此总体复杂度为 \(O((S+n\log S)\log m)\) 实际上常数非常大？