Michael_Bryant最喜欢的G(al)G(ame)

那些悲伤,那些寂寞,那些几乎让自己放弃生活的希望的痛苦的回忆,绝对绝对不要将它们忘记。

Michael_Bryant最喜欢的番剧

抱歉⋯我已经绝对不可能再获得幸福了,因为⋯我发现⋯ 其实我⋯ 早就已经被幸福包围了

Michael_Bryant正在看的番剧

死亡一点也不温柔,只有无尽的黑暗和孤独。 就算联系得再紧密,人也是孤独的。

浅谈KMP算法,TRIE树,MANACHER

写在前面

这几个字符串算法
都是非常基础的
写在这里就是为了凑文章数量
不然博客太单薄了

I.KMP

看毛片KMP算法用来解决两个串的匹配问题
正常我们匹配一个串
要用一个非常简单的方法
就是非常暴力的把每一位匹配一下
下面是这个毫无意义的图(这个东西想不出来的可以不用听了

就这样
非常暴力的做法
找到每个位置都匹配一遍
然后你就FFT了
FAST_FAST_TLE
所以接下来引入了KMP算法
这个KMP吧 挺简单的
不过真的很有用的
这个KMP吧是拿来处理字符串匹配的。也就是给你两个字符串,你需要回答,B 串是否是 A 串的子串(A 串是否包含 B 串)。比如,字符串 A="I'mmatrix67",字符串 B="matrix",我 们就说 B 是 A 的子串。我们称等待匹配的 A 串为主串(母串),用来匹配的 B 串为模式串。 解决这类问题,通常我们的方法是枚举从 A 串的什么位置起开始与 B 匹配,然后验证 是否匹配。假如 A 串长度为n,B 串长度为m ,那么这种方法的复杂度是 O(mn) 的。虽然
很多时候复杂度达不到(验证时只看头一两个字母就发现不匹配了),但我们有许多“最坏 情况”,比如, aaaaaaab aaaaaaaaaaA  , ab aaaaaaaaaaB  .我们将介绍的是一种最 坏情况下O(n) 的算法(这里假设 m<=n ),即 KMP 算法。
假如,A="abababaababacb",B="ababacb",我们来看看KMP是怎么工作的。我们用两个指针i和j分别表示,A[i-j+ 1..i]与B[1..j]完全相等。也就是说,i是不断增加的,随着i的增加j相应地变化,且j满足以A[i]结尾的长度为j的字符串正好匹配B串的前 j个字符(j当然越大越好),现在需要检验A[i+1]和B[j+1]的关系。当A[i+1]=B[j+1]时,i和j各加一;什么时候j=m了,我们就说B是A的子串(B串已经整完了),并且可以根据这时的i值算出匹配的位置。当A[i+1]<>B[j+1],KMP的策略是调整j的位置(减小j值)使得A[i-j+1..i]与B[1..j]保持匹配且新的B[j+1]恰好与A[i+1]匹配(从而使得i和j能继续增加)。我们看一看当 i=j=5时的情况。

i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
此时,A[6]<>B[6]。这表明,此时j不能等于5了,我们要把j改成比它小的值j'。j'可能是多少呢?仔细想一下,我们发现,j'必须要使得B[1..j]中的头j'个字母和末j'个字母完全相等(这样j变成了j'后才能继续保持i和j的性质)。这个j'当然要越大越好。在这里,B [1..5]="ababa",头3个字母和末3个字母都是"aba"。而当新的j为3时,A[6]恰好和B[4]相等。于是,i变成了6,而j则变成了 4:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
从上面的这个例子,我们可以看到,新的j可以取多少与i无关,只与B串有关。我们完全可以预处理出这样一个数组P[j],表示当匹配到B数组的第j个字母而第j+1个字母不能匹配了时,新的j最大是多少。P[j]应该是所有满足B[1..P[j]]=B[j-P[j]+1..j]的最大值。
再后来,A[7]=B[5],i和j又各增加1。这时,又出现了A[i+1]<>B[j+1]的情况:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
由于P[5]=3,因此新的j=3:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
这时,新的j=3仍然不能满足A[i+1]=B[j+1],此时我们再次减小j值,将j再次更新为P[3]:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 1 2 3 4 5 6 7
现在,i还是7,j已经变成1了。而此时A[8]居然仍然不等于B[j+1]。这样,j必须减小到P[1],即0:
i = 1 2 3 4 5 6 7 8 9 ……
A = a b a b a b a a b a b …
B = a b a b a c b
j = 0 1 2 3 4 5 6 7
终于,A[8]=B[1],i变为8,j为1。事实上,有可能j到了0仍然不能满足A[i+1]=B[j+1](比如A[8]="d"时)。因此,准确的说法是,当j=0了时,我们增加i值但忽略j直到出现A[i]=B[1]为止。
最后的j:=P[j]是为了让程序继续做下去,因为我们有可能找到多处匹配。
这个程序或许比想像中的要简单,因为对于i值的不断增加,代码用的是for循环
。因此,这个代码可以这样形象地理解:扫描字符串A,并更新可以匹配到B的什么位置。
现在,我们还遗留了两个重要的问题:一,为什么这个程序是线性的;二,如何快速预处理P数组。
为什么这个程序是O(n)的?其实,主要的争议在于,while循环使得执行次数出现了不确定因素。我们将用到时间复杂度的摊还分析中的主要策略,简单地说就是通过观察某一个变量或函数值的变化来对零散的、杂乱的、不规则的执行次数进行累计。KMP的时间复杂度分析可谓摊还分析的典型。我们从上述程序的j 值入手。每一次执行while循环都会使j减小(但不能减成负的),而另外的改变j值的地方只有第五行。每次执行了这一行,j都只能加1;因此,整个过程中j最多加了n个1。于是,j最多只有n次减小的机会(j值减小的次数当然不能超过n,因为j永远是非负整数)。这告诉我们,while循环总共最多执行了n次。按照摊还分析的说法,平摊到每次for循环中后,一次for循环的复杂度为O(1)。整个过程显然是O(n)的。这样的分析对于后面P数组预处理的过程同样有效,同样可以得到预处理过程的复杂度为O(m)。
预处理不需要按照P的定义写成O(m^2)甚至O(m^3)的。我们可以通过P[1],P[2],…,P[j-1]的值来获得P[j]的值。对于刚才的B="ababacb",假如我们已经求出了P[1],P[2],P[3]和P[4],看看我们应该怎么求出P[5]和P[6]。P[4]=2,那么P [5]显然等于P[4]+1,因为由P[4]可以知道,B[1,2]已经和B[3,4]相等了,现在又有B[3]=B[5],所以P[5]可以由P[4] 后面加一个字符得到。P[6]也等于P[5]+1吗?显然不是,因为B[ P[5]+1 ]<>B[6]。那么,我们要考虑“退一步”了。我们考虑P[6]是否有可能由P[5]的情况所包含的子串得到,即是否P[6]=P[ P[5] ]+1。这里想不通的话可以仔细看一下:
. . . . 1 2 3 4 5 6 7
B = a b a b a c b
P = 0 0 1 2 3 ?
P[5]=3是因为B[1..3]和B[3..5]都是"aba";而P[3]=1则告诉我们,B[1]、B[3]和B[5]都是"a"。既然P[6]不能由P[5]得到,或许可以由P[3]得到(如果B[2]恰好和B[6]相等的话,P[6]就等于P[3]+1了)。显然,P[6]也不能通过P[3]得到,因为B[2]<>B[6]。事实上,这样一直推到P[1]也不行,最后,我们得到,P[6]=0。
诸如此类 我们就得到了最终的匹配
上面是他的复杂度证明
上面提到的预处理跟主程序神似
其实说白了这个函数的预处理就是一个自我匹配的过程
最后的补充
由于KMP算法本身的算法
这个做法对于一类题目特别优
给定一个B串和一堆A串
然后求解B串是哪些A串的子串
KMP,Trie树, AC自动机_commonc
例题在这里不给出 需要的话底部评论私聊我
我真的不知道有什么题好讲的
就用fzoj那道得了

II.Trie树

这棵树可以往上面T一点东西
比如说字符串
我们在做的时候保证具有公共前缀的东西拥有共同的祖先
这样的话我们在处理的时候相同的前缀不用进行多次处理
以下面为例

这是五个单词 she say him did dig
我们看到所有的公共前缀都到了一起
这样也节省空间
就是这么simple
KMP,Trie树, AC自动机_commonc
字典树没什么多说的
主要是两个应用
第一个查询单词A是不是单词B的前缀
第二个是跟我接下来的AC自动机有不可脱离的关系
还是 例题不给出 需要评论
这个真没有例题
(除了裸题

III.manacher

这个算法主要用来处理回文串问题
具体操作就是
操作流程:
manacher,后缀数组_commonc
还是跟上面一样
例题:
给出两道
1.最长双回文串
2.POI一道题 懒得找名字了

IV.写在最后

1.以上PPT来自NKC这个jl
2.谢谢大家

Add a Comment

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

隐藏