【复习笔记】2021-12 字符串

本文主要是记录复习模板的情况


后缀自动机

  • 线段树维护 endpos 例题

  • 计算子串在多少个模板串中出现,可以建立广义 SAM 后对于每一个模板串找到其所有前缀在广义 SAM 上的节点,然后从它们开始暴力跳 parent 树算贡献,并给每个访问了的节点打*问标记保证在同一个模板串的计算过程中一个点不经过两次的做法复杂度为 \(\Theta(n\sqrt n)\),证明考虑根号分治

  • 先区别叫法:按照正序加入自动机再连接 \((i,fail_i)\) 得到的树是 \(\rm{Parent\ Tree}\),而逆序加入得到的是后缀树

  • 在 \(\rm{Parent\ Tree}\) 上跳 \(\rm{fail}\) 表示取后缀,走自动机上的出边表示在当前字符串后面添加字符,在后缀树上进行这些操作含义同但是方向完全取反

  • 在 \(\rm{Parent\ Tree}\) 上根链操作表示将这些后缀进行一次在当前最后一次出现位置上进行更新:出现次数的增加/更新最后一次出现位置

  • 广义 \(\rm{SAM}\) 的可能正确写法是加入的时候判断 \(\rm{las}\) 是否已经有这个儿子,也因此可以任意调整 \(\rm{las}\) 的值进行加入新点,可以应用于 \(trie\) 树上建后缀自动机

  • 用 \(\rm{LCT}\) 维护 \(\rm{SAM}\) 得到的 \(parent\) 树或者后缀树是一个常见技巧

    基于是不是强制在线要求是不是需要写 access 之外的函数,Luogu7361 是统一处理,可以离线,而另外的 \(\rm{Luogu}5212\) 不行,需要写全套

  • 使用 \(\rm{Parent\ Tree}\) 或者后缀树维护字典序(例如求 \(\rm{SA}\))

    对于树上同一节点的子节点的代表元是 \(\rm{str[len[fa[x]]+pos[x]]}\),连边的时候排序即可

    直接求 SA 需要注意比较的是前缀信息,所以使用的是倒序建立的后缀树

Luogu5115

可能的计算答案方式并不多,尝试按照位置统计贡献失败之后转行来按照每个字符串来统计贡献

观察一下一个特定长度的字符串会带来多少的贡献:

\[\sum_{i=1}^{len}(len-i+1)i[i\le k_1][len-i+1\le k2] \]

当 \(len\leftarrow len+1\) 时,增量只有三种:添加 \(i=len+1\) 的贡献/删掉 \(i=len+1-k_1\) 的贡献/\((len-i+1)i\) 的变化量,可以 \(\Theta(n)\) 递推得到

剩下的问题就是每个字符串在统计进答案的时候一定要保证是极长的,由于 \(endpos\) 的原因,在节点对应的字符串前面加入相同字符不再可行,但是可以在后面加

注意到 \(SAM\) 每个节点可以维护出来对应在原字符串中的后面一个字符,于是每次统计的时候用总的对数减去后继相同的对数即可

时间复杂度 \(\Theta(n\Sigma)\)

Luogu7361

能离线就离线,所以扫描线,观察添加最后一个节点会带来哪些字符串出现了第二次

首先在 \(\rm{LCT}\) 上面维护第一次/第二次出现的位置,此时每个 splay 上的点最后一次出现次数相同

不难发现在 access 的过程中,跳虚边的父节点是能经过的链上的字符串长最大值,又由于最后一次出现节点被更新成一样的了,又因为是在同一个 splay 上,更新前视角下最后一次出现也是一样的,所以它可以代表整个 splay 来更新

此时考察答案的形式:一个节点代表的字符串被完全包含在区间里面/被部分包含

如果完全包含直接用 \(len[x]\) 更新答案,否则用 \(\rm{last-left}\) 来更新

由于是扫描线,所以维护两个线段树维护两种情况下最大值,每次跳虚边时给能更新的更新即可

注意不能包含时对答案的贡献一定是 \(\rm{rpos-queryl}\) 而每个叶子对应的 \(\rm{queryl}\) 一定,所以维护 \(\rm{rpos}\) 最值

Z-Function

Z 函数算法本质是减少冗余,尽可能利用已经计算过的信息

if(i<=r) z[i]=min(r-i+1,z[i-l+1]); 一句中就很好体现了这点 ,这也恰好保证了整个处理过程复杂度

CF432D

主要是处理前缀在字符串中出现次数:

z[i] 计算的是每个后缀和全串的 \(\rm{LCP}\),那么对于一个前缀 \(S[1\dots l]\),满足 \(z_j\ge l\) 的 \(j\) 为起始点,必然出现了一次

不难发现子串在母串出现必然有唯一起始点,所以该做法可以不重不漏统计

直接对 \(z_i\) 开桶然后后缀和即可

AC 自动机

  • 对 Fail 树根链更新表示更新该串子串信息

Luogu

上一篇:一图解决PR/PO关联业务中所有参与者信息同步的痛点


下一篇:【笔记】联通分量/2-SAT