「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)$ 实际上常数非常大？