• 周五. 12月 2nd, 2022

5G编程聚合网

5G时代下一个聚合的编程学习网

热门标签

串串题-各种算法的应用

admin

11月 28, 2021

如题,这篇主要讲字符串题,偏应用,与思维方式

原本是对着NOI大纲上字符串那一栏做的,并自己把SAM和SA强行加进来了,因为我觉得它们也应该在字符串这一栏讲。

这一部分基础知识大多比较简单,很多人都会,所以我们来讨论如何灵活的运用它们。

哈希

这个应该人均会

哈希+思维: NOI2016优秀的拆分

(f(i),g(i)) 表示 (i) 位置向前/向后形如 (AA) 的串的数量。那么答案为 (sum f(i) imes g(i+1))

(f,g) 没有本质区别。考虑求 (f)(g) 反过来做一遍就行。

我们枚举 (A) 的长度为 (i),然后考虑每隔 (i) 个位置就打一个标记。

然后观察性质发现,任意选一段 (AA) 串,一定会经过恰好两个标记。两标记以前的位置,是一段LCS;两标记以后的位置,是一段LCP。

那我们就枚举相邻两个标记,看 LCP+LCS 是否比 (i) 大就行了。

哈希一波,或者SA一波,就能 (O(log n)/O(1)) 的算 LCP 和 LCS,然后算标记的复杂度是调和级数,就能通过本题。

KMP

KMP,简单吧,超级简单,不用讲了

有时,越是以为简单的东西,越不简单。尤其是一个算法,如果和思维结合起来,就会变的他妈都不认识

KMP+思维: Fibonacci words

我一开始想了好久,想了各种神秘字符串结构,都⑧行

一看题解,竟然只需要KMP

首先对于两个串 (A,B),在里面匹配 (T),我们可以在 (A,B)​ 中分别匹配,然后处理一下跨区间的匹配。设 (f_n)

表示 (T) 在串 (F_n) 中的匹配。

那么 (f_n=f_{n-1}+f_{n-2}+I(F_{n-1},F_{n-2})), (I(A,B)) 表示 (T) 跨越 (A,B) 的匹配。

对于这个递推式,前两项我们可以直接加,关键在于后面的那个 (I)。注意到,当 (F_n) 开始比 (T) 长的时候,它中间的很长一段咱都不要了,只保留 长度为 (T)​ 的前后缀就行。每次匹配就暴力跑个 KMP,反正咱已经把串长降下来了。这样复杂度就是 (O(nT)) 的了。

利用fail: CF432D

这是一个经典套路:把KMP的fail数组建成树,称 “失配树”,或者fail树

我们注意到,ACAM,PAM,SAM里面都有fail树的说法。所以这个KMP其实也是个自动机,可以认为是这样:

对于我们的模式串 (T)

  • (x) 表示,当前串能匹配到 (T[:x])
  • 节点之间有着一些边:(xxrightarrow[]{T_{x+1}} x+1)
  • 有一种fail边,当字符边不匹配的时候,就走fail边,再看能不能匹配

那这么说把fail树建出来有什么用呢?

有着以下几个性质:(暂时只有一个,等待补充)

  • (i) 节点的子树size,就是前缀 (i) 在串中出现的次数

然后就可以解决掉CF432D这个题了

Trie 字典树

trie本身很sb,相信大家都会

利用trie结构解决字典序的限制: USACO2012 First!

先建好fail树,考虑每个串。

如果它要成为最小的那个串,我们就需要手动调整字母表的顺序。

在trie树上看,假设在某一层,当前串的对应位上,字符是 (c),那这个 (c) 就要比当前节点所有兄弟节点对应的那个字符 (c’) 要 “小”。(带引号的“小”表示,在我们自定义的顺序中的小于)

形式化的说,我们枚举一个串 (s),然后在trie上走,上一步走到 (u),当前字符是 (c)(u)(c) 边走到 (v),就是当前位置。

(forall c’
eq c)
(u) 存在 (c’) 转移,转移到 (v’)(c) 要“小于” (c’)

这很显然,对于这些 (v’) 对应的串,设为 (s’) ,和 (s) 的 LCP 显然就是 (u) 对应的那些串,而它俩第一个不同的字符就是 (c)(c’)。我们要让 (s) “小于” (s’),那么 (c) 就要 “小于” (c’)

我们这样跑下来,会建立最多 (inom{26}{2}) 个关系。跑一遍拓扑排序,只要不存在环,就是合法的。

复杂度 (O(sum S imes A^2))(A) 为字符集大小 ,(A=26)

Suffix Array(SA) 后缀数组

不会的看 这里

注意,SA的复杂度和字符集大小并没有很大关系,就算是一个整数序列也可以跑SA。

SA+并查集: poj1743

SA有一个很常见的trick,就是用并查集把height>=k的位置并起来考虑。

那怎么解决这个题呢?

我们转化一下“相似”这个条件,注意到两个序列如果可以通过整体加某个数得到,那么它俩差分除了第一个位置都相同。

那我们相当于在差分序列上求最长的两个子串,使得它俩相同,并且不相交。

倒着枚举长度 (k)。每次把height=k的两个位置并起来,那每次就相当于height>=k的位置并在一块。

height>=k,就说明有一个长度为 (k) 的子串,在这些位置 全部 都出现过。

然后我们维护一下每一块里的最小、最大位置,看看它俩的差是不是 (>k) 就行了。

其实这个合并的过程,如果一次合并多个叉,就相当于是建后缀树的过程

SA+思维: CF319D

我们可以这样考虑:枚举长度 (i:1…n),把长度 (=i) 且相邻连续出现两次的串 一块 删掉,复杂度是多少?

看起来好像是 (O(n)) 的。但是,有效删除(删除至少一个位置的操作)次数,其实是 (O(sqrt{n}))

注意到 1+2+3… 这个东西是平方级别增长的,要超过 (n) 也只需要 (O(sqrt{n})) 的级别。

那我们怎么算相邻连续出现两次的串呢?

往上翻到NOI2016优秀的拆分,打标记就行。

注意精细实现:只有每次 有效删除 之后重构SA,其它时候就打标记看看有没有解。

复杂度是 (O(nsqrt{n}+nlog n)=O(nsqrt{n}))

树上SA: gym 102511G

我们把串反过来之后,发现,“加前面”变成“加后面”,然后就可以建出一颗trie树来,尽管我们不能直接存下每个串。

然后,“问前缀”也就变成了“问后缀”

那这个咋做呢?

我们发现,还是“问前缀”好做。于是我们考虑,在trie树上,从下到上 还原这些串,并搞出一个结构,支持前缀的查询。

很明显我们不能把每个串都搞出来,也不太方便建一个trie出来。那么什么结构可以支持前缀的查询呢?

SAM! —— 很明显建不出来

SA!—— 建不出来,吗?

普通的SA是在序列上倍增,我们考虑 在树上倍增,建SA

很好搞,就记一个倍增跳祖先的数组 (jump(u,i)),表示 (u)(2^i) 级祖先。然后把 ((rank(u),rank(jump(u,i)))) 这个 pair 搞一个基数排序就行了。时间复杂度是 (O(nlog n))(n) 为 trie 上的节点数。

本题的关键在于想出 “树上倍增建SA” 这个事情,想到了之后就迎刃而解了。

Suffix Automaton (SAM) 后缀自动机

不会的看 这里

SAM维护子串的匹配: USACO2010 Threatening Letter

SAM是一个可以接受所有子串的自动机。

那它就可以像KMP一样,维护一个 子串的匹配

如这个题,有一个明显的贪心策略:

设打印好的信件那个串是 (S),FJ要发的内容是 (T)

每次在 (T) 找到最长的一个前缀使得它是 (S) 的子串,然后划一段,就行了

为啥?很明显,如果我们能划一个串,就能划它任意的子串,因为子串的子串还是子串。那我们让剩下的尽可能少,就是最优的。

(S) 建一个 SAM,用 SAM 维护这个匹配就行:每次在自动机上走不动了,就划一段,并回到初始节点

发表回复

您的电子邮箱地址不会被公开。 必填项已用*标注