SOSUSOSU

假装这是一个正经的页面

[嘴]字符串算法小讲

前言

我还记得我刚开始搞oi的时候立下的flag:总有一天我要把我会的所有算法都写出来为后来的oier们留下宝贵的财产!

后来事实证明这确实是一个flag,蠢兮兮的23333333

那么闲话说完我们来看看今天嘴些什么东西:

标题内容

kmp/exkmp,ac自动机,后缀自动机

啊其实字符串算法还有很多很多,什么后缀数组啊,踹树啊,什么马拉车啊回文树回文自动机啊,什么后缀树啊这些,为啥不写呢,因为其中有些太简单而有些我又不会(后缀数组,回文相关),要讲当然是要讲我会的啦!

个人现在认为这几个算是够用的(如果今后发现不够用了会回来补的emmmm),以上。

kmp/exkmp

kmp和exkmp算法都是利用了已知的信息除去多余的操作,而未知的信息在变为已知的时候都只经过了一次操作,所以保证了时间复杂度是线性的。

kmp

记得我一开始学算法的时候,都是跑到网上一通乱搜,然后看着人家写的各种理解分析教程之类的,看过之后往往算法没有学会,反而被很多人不同的理解搞的头昏脑胀,也时常感慨程序员的语文大概都是计算机老师教的吧。

总之后来在接触过很多算法之后,我觉得有时候看一堆算法原理倒不如把模板拉出来,搞清楚每个变量到底代表的是什么,然后再去理解算法的原理。

那么我们的kmp算法,作为一个1对1匹配的,复杂度为O(n)级别的算法来说,它的核心在哪?在一个next数组。

首先我们定义两个串,一个a串长为n,一个b串长为m,我们用b串去和a串匹配,比方说求a串中有多少个b串。

如果是暴力匹配,那么复杂度就到了o(nm)级别,然而这nm次操作中有很多操作可以省略,于是我们就找到了next数组来帮我们简化这些冗余的操作,将复杂度降为o(n+m)。

何为next数组?在我理解的kmp里,next[i]代表的是从i这个位置往前有至多next[i]个字符可以作为原串的前缀。

比如b串是xyzxyz,那么它的next数组就是000123,当i等于5时,意味着xy是b串中以位置5为结尾的可以作为xyzxyz的前缀的最长串,就是b[i – next[i]+j]=b[j](1<=j<=next[i])。

然后我们处理出b串的next数组后,再用b串去匹a串,假设a串是xyzxym,b串还是xyzxyz,如果当前位置匹配就往后走,当走到不匹配时,z和m不一样了,我们去找next[5]=2,也就是说从b串第5个位置跳到了第2个位置,从xyzxy到了xy,如果匹配失败就按next跳过去,直到匹配成功或者b[1]!=a[now],那么我们就放弃这个a[now],去从a[now+1]开始匹配。

至于时间复杂度为什么降下来了,看代码就一目了然,pro++的操作是O(n)级的,虽然有while但是pro=next[pro]的操作也是O(n)级的(啊dalao们可能都知道)。

以上,kmp就这样了,有了next数组可以用kmp解决很多问题啦!

exkmp

啊exkmp!exkmp是求匹配串某位置往后能有最长多长的串可以作为原串的前缀,最后求出来答案是extend数组。

比如说匹配串是121212,原串是12,那么最后求出来的extend数组就是202020,第一个位置往后12和12是一样的,第二个位置是2,和原串第一个1是不同的,所以它往吼就不能匹配咯,extend[2]=0。

然后exkmp主要中的next数组和extend数组意思差不多,可以说next是原串自己匹自己的extend数组。

exkmp有两个值,一个pro维护当前extend[i]+i最大的i,而prov是维护这个最大的extend[pro]+pro。

exkmp依旧是通过记录扫过的信息来使得每个点只会被扫到一次,使时间复杂度保持在O(n)级。

这个prov可以看做当前扫到的最远的位置,扫到是指在串匹配时字符匹配就向后扫一位,而不是当前更新next数组或extend数组的位置。

比如当前要为now更新next数组,那么查找now-pro+1位置的next数组,因为now相对于pro的位置和now-pro+1相对于原串起点的位置是一样的,信息可以作为参考。

于是我们通过这样的操作便可以通过已有的信息快速处理出新的信息,避免了冗余的操作。

剩下的细节就让代码来说吧。

AC自动机

ac自动机是Aho-Corasick automaton不是自动ac机

ac自动机是一个优秀的1对多/多对1的字符串匹配算法,它基于trie(踹)树,像kmp的next数组一样,通过匹配失败后的指针跳跃到上一个点,继续匹配,从而达到简化冗余匹配的效果。

ac自动机依然是优秀的线性算法。

有限状态自动机

有限状态自动机是一个可以识别字符串的自动机,令A为有限状态自动机,若它能识别S串,则定义A(S)= true,若它不能识别T,则定义A(T)=false。

trie树

trie树是一个树(不知道树请自觉右上角),它从根节点到某树的节点的路径上,所有的边所代表的的字母连接起来便是一个字符串。

fail数组

fail数组存储的是若当前点的下一个字符匹配失效,则跳转到的上一个点,如果你已经认真的阅读了上文的kmp算法,那么fail数组和next数组的作用是相同的,只是fail指向的是树上的节点,而next数组所指是单个字符串中的位置。

构建ac自动机

1.把串们全部丢到trie树中。

2.bfs  trie树,若当前为now点,i表示字符集s中第i个字符,t[now][i]表示当前的串加上s[i]后的串在trie树中所代表的节点,若该点不存在(t[now][i]为空),直接将t[now][i]这个空点指向t[fail[now]][i];若该点存在,将该点的fail指向t[fail[now]][i],即fail[t[now][i]]指向t[fail[now]][i]。

run!

啊,我们按刚才的方法建好ac自动机后,直接跑啊!不要问!就是直接跑,什么别的操作都没,朴素的匹配就行!

啊现在看起来ac自动机好简单啊。。。没啥好说的,不过ac自动机上边还能跑dp啥的,剩下的都是就题论题,到时候再说吧!

看一道模板题:

后缀自动机SAM

啊终于说到我最喜欢的山姆自动机啦!其实前边几个我不是很懂emmmm。。。乱嘴了一堆qwq

先贴陈老师的ppt,个人理解可能比较肤浅,如果我讲的太菜请去膜陈老师qwq

那么后缀自动机是什么?

后缀自动机,Suffix Automaton。字符串S的SAM是一个可以识别S的所有后缀的自动机。

一个长为n的串有n个后缀,如果像上文ac自动机将这n个串都扔到trie树中,时间/空间复杂度就都到了n^2级别,很GG。

而我们的SAM又是一个优秀的线性算法,可以用来处理一个串所有的后缀。

先贴我敲的模板,因为SAM东西有些多,所以我觉得先从代码入手会更好理解一些。

啊看起来就很短很优美(跑

构建后缀自动机

1.按顺序将字符丢进后缀自动机。

2.设当前丢进去的是第now个字符,建立新的节点np,step=now,right[np]=1,np的父亲为上一个字符加进来时所建立的节点last,令pro为当前字符now在字符集中的位置。

3.若np的父亲p没有连向p的边,!ch[p][pro],那么往p的父亲去找,p=fa[p],一直跳,直到有这条边或者不能再跳。

4.(啊等晚上回去再写吧!)

 

点赞

发表评论

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