借此机会也强制自己学一点东西。

Trie

模板

Tire即前缀树,用来保存字符串集合。

  • \(ch[i][j]\)表示Trie中结点\(i\)的孩子\(j\)的编号
  • \(val[i]>0\)表示结点\(i\)为一个单词的结尾结点

题目精选

1.【LA3942】Remember the Word

令\(f[x]\)表示从第\(x\)开始的字符串(即\(S_x\)…\(S_{len(s)}\))的拆分方案数。

我们可以枚举每个单词,然后判断\(S_x\)…\(S_{len(s)}\)的前缀是否包含他。这样的时间复杂度显然是不行的。

我们可以把所有的单词丢到Trie上,在Trie上跑dp。

从\(S_x\)开始,在Trie上做匹配,匹配成功的所有位置的深度\(y\)(就是匹配成功的长度),则\(f[x]=\sum f(x+y)\)。

时间复杂度\(\mathcal{O}(|S|*max_{i=1}^{n}{|s_i|})\)。

2.【Leetcoder421Maximum XOR of Two Numbers in an Array

把所有的\(a_i\)拆成二进制,高位在前低位在后看作字符串,插入Trie。

对于每一个数\(a_i\),从高位到低位在Trie上跑,贪心的尽量向每一位 xor 结果为\(1\)的子树上跑。

时间复杂度\(\mathcal{O}(n*log_2(max{a_i}))\)。

当然这道题目是有别的解法的,这里就不提了。

3.【NEERC11D】Dictionary Size

考虑不重不漏的计数方法。

即把一个单词分为两部分,使得前一部分为某一单词的前缀,后一部分为某一单词的后缀。

我们希望第一部分尽量地长,也就是令前缀极长,这样就可以保证不重复。

不过这样处理的话有一个问题:

如果有两个单词分别是 {back,c}

那么对于 bac 的分割,ba|c的分割不满足前缀极长,而bac|的分割,后边一个为空,不符合要求

仔细考虑出现这种情况的原因,是因为这个词是本身不是字典词,但是他的非空前缀,并且单词的最后一个字母是合法的后缀,这种情况特判即可。

我们把所有的字典次插入Trie,当遍历到一个结点\(x\)没有没有孩子\(c\)的时候,统计以\(c\)开头的所有合法后缀即可。

统计合法后缀的方法是,将所有单词倒序插入另一棵Trie。

不要忘了特判上面那种情况即可。

 

 


AC自动机

一种字符串的快速匹配算法。适用于多模式串的匹配。

AC自动机是Trie加上失配边组成的。

所谓失配边,即是在当前位置向下匹配的时候失败了,把正在匹配的原串向后至少移动多少位置,可以使原串的前缀和当前模式串的某一段匹配。所以失配边指向的是接下来可以继续向下匹配的位置,一定是由深度深的点向深度欠的点指的。

和Tire不同的是,Trie的结点\(x\)如果满足\(val[x]>0\)那么表示从根到\(x\)是一个单词。

但是AC自动机里面,每一个结点不再仅仅是一个单词的结尾,它还包含了所有以他为结尾作为前缀的串。

比如上图的\(5\)结点,他既表示 she ,也表示he。

如果 she 继续匹配失败了,那么 he 仍然是成立的。所以\(5\)结点除了记录是 she 的结尾,也应该记录,当从\(5\)走失配边的时候,下一个单词是什么,这个例子里,就是 he。

我们用\(last[x]\)表示从\(x\)走失配边的时候,遇到下一个单词结点的编号,这个专业名次叫做后缀链接(suffix link)。

题目精选

1.【LA4670】Dominating Patterns

纯模板题。

把模版串建出AC自动机,然后拿原串在上面跑就行了。

只需要写一个计数的函数就搞定了。

2.【JSOI2007】文本生成器

用AC自动机处理所有了解的单词

显然,不能直接算,直接算的话,我们需要大力容斥,复杂度不允许

我们不妨反过来做,我们根据AC自动机处理出所有的不可行解,然后用总数减去即可

计算所有不可行解用dp,\(f[i][j]\)表示处理到字符串第\(i\)位,在自动机上第\(j\)个节点的不可行方案数,直接暴力转移即可。

3.【2018 ACM-ICPC Beijing Onsite H】Approximate Matching

暴力修改串\(T\)的每一位以及\(T\)本身,将得到的所有新串加入 AC自动机

令\(dp[i][j]\)表示\(S\)串的\(i\)个字符,匹配到自动机的\(j\)号节点上,不满足条件的字符串\(S\)个数

显然最后的答案就是\(2^m-\sum_{i=1}^{cnt}dp[m][i]\)(\(i\)号节点不是某个单词的末尾)

直接在AC自动机上暴力转移就好了。

赛场上的代码显然不在了。那就。找了一份做法一样的。

 


KMP算法

(KMP部分的图片均引用自《算法导论》)

和AC自动机类似的,KMP算法也是一种字符串匹配算法。

只不过KMP适用于单模式串的匹配。而且KMP的next数组应用非常玄学。

可以发现,对于简单的字符串匹配算法,时间大规模的浪费在了重复的比较匹配上面,那么KMP算法用巧妙的预处理将重复的比较省去了。

如下图,在匹配到第六个字符,出现错误,而已经有了\(5\)个匹配字符的信息,我们可以根据这个信息,推知\(s+1\)的偏析是无效的,而\(s+2\)的偏移是会有三个字符匹配的,只要从第四个字符开始比较即可。

那么,我们和AC自动机类似的,我们需要知道失配以后的偏移情况。

所以我们需要预处理在比较时发生的偏移,下图是一个例子:

可以看到\(\pi [x]\)表示的是,在\(x+1\)位置失配以后,\(x\)位置所对应的位置可以变为模式串的哪一位。

这里的\(\pi [x]\),也就是我们一般而言的next数组,我们称它为偏移数组。

模板

下面的字符串,我们都假设主串长度为\(n\),模式串的长度为\(m\)

显然,一个偏移位置就是以\(x\)为结尾的后缀和模式串前缀的极大匹配量,我们可以\(O(m)\)预处理出来。

需要注意的是,Next数组要比字符串多一位,最后一位表示的是全部匹配以后的偏移。

得到了偏移数组,匹配算法就比较显然了。

两个参数\(W\)和\(T\)分别是主串和模式串

由此可知,KMP算法的预处理时间复杂度是\(O(m)\),匹配的时间复杂度是\(O(n)\),所以总的时间复杂度就是\(O(n+m)\)。

完全的匹配已经没有什么讲的意义了。我们来看一看Next数组的应用。

题目精选

1.【HDU3336】Count the string

前缀匹配成功的次数,我们可以利用Next数组。

根据Next数组的性质知,当Next数组有值的时候,就证明肯定有一个匹配,所以我们需要统计出Next数组里面\(>0\)的个数

但是一个\(>0\)Next数组位贡献可能不止1,因为他本身后缀的前缀可能也是一个符合要求的

所以我们对于每一个\(>0\)Next数组位需要向前探查有多少符合要求的前缀,就是他的贡献个数

再加上与自身的匹配\(n\)就是答案

2.【ZOJ1905Power Strings

Next数组的经典应用,求最短的循环节,可以得到是\(len-Next[len]\)。

那么存在循环节的条件自然就是,\(len\)能够整除\(len-Next[len]\)。

证明就略了。直观感受以下也不难。

3.【POJ2752Seek the Name, Seek the Fame

显然\(S_1,\cdots ,S_{Next[i]}\)和\(S_{len-Next[i]+1},\cdots ,S_{len}\)是最长公共前后缀

显然\(S_1,\cdots ,S_{Next[Next[i]]}\)和\(S_{len-Next[Next[i]]+1},\cdots ,S_{len}\)也是公共前后缀

如此反复的话,我们直接递归调用即可。

别忘了自己本身也是公共前后缀。

 


 


发表评论

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