《字符串的有关算法讲述课件》由会员分享,可在线阅读,更多相关《字符串的有关算法讲述课件(98页珍藏版)》请在金锄头文库上搜索。
1、字符串的相关算法还是在前面的话因为本人太弱所以这几天讲的ppt经常会发现错误,建议在ppt大略的基础上去找相关论文学习。可能重点还是在原理的简单解释有的地方听不懂的话也没关系,因为每个人没有实现过代码之前实际上都是这样的,可能会对某些地方不理解不影响你对整个算法的印象。以后如果能够专门思考的话也许就会快捷许多。字符串算法有一些的原理看起来比较麻烦,但是代码量往往特别短,所以建议要去完全理解某个算法的原理,这样子以后就算把模板忘了,也许也能够通过原理写出相应的代码。一开始可以学习一下练习模板。字符串算法的模板往往很短,很容易上手。大前天提到了分治提到了这样一个方程f(n)=f(n/2)+f(n/
2、2)+O(1)这个咱当时是说f(n)=O(nlogn)那是咱SBToo Nave考虑线段树的节点,就是这个分布的可是线段树的节点个数是O(n)的这个的解显然应该是f(n)=O(n)在此表示歉意咱所知道的字符串算法Pascal的Pos函数Hash哈希Kmp和扩展KmpTrie树AC自动机后缀树,后缀数组(SA),后缀自动机(SAM)Manacher算法乱搞最近新出来的:回文自动机(PAM)(太弱不会)。Hash哈希Hash应该都知道常用的Hash函数?首先直接把每一个字符的ASCII值加起来作为Hash值不取模的情况很容易冲突常用的Hash,自己设一个X进制(X=你的字符集的大小-1,比如大写字
3、母有26个字母,字符集大小为26)然后咱们就有 Hash=Si*X(i-1)假设字符串长度为s,这个就可以在O(s)的时间内算出来。显然如果存的下最后的Hash值的话,每一个字符串的Hash值必定不相同。Q:为什么?实际上这种计算方法,每个字符串都是X进制下的一个数,而Hash值就是这个X进制的数转十进制的值,由于X进制的数互不相同,显然Hash值,即十进制的数也互不相同。Q:那如果字符串长度过大,以致会爆怎么办?取个模呗Q:那如果两个字符串不同Hash值取某个模最后相同怎么办?取多个模呗如果多个模的情况下都相同那么就是同一个字符串。Q:如果取多个模都相同呢?首先,这个模是你自己定的,所以一般
4、数据是没办法全部卡的。接着,由中国剩余定理,只要取到的每个模足够大,那么最后也可以保证一定范围内的Hash值是一定的。Q:中国剩余定理是什么?以后讲数学的时候会讲吧顺便可以百度_(:)_除了这种Hash以外,字符串Hash也有很多其他的版本,比如ELFhash(黑书上的)据说这个的效果比上面的还好,咱没试过_(:)_Function ELFhash(var s:string):integer;Var g,h,i:longint;Begin h:=0; for i:=1 to length(s) do begin h:=h shl 4+Ord(Si); g:=h and $f0000000 ($
5、是十六进制) if g0 then h:=h xor (g shr 24); h:=h and (not g); end; ELFhash:=h mod M;End;Bzoj1014 JSOI2008 火星人火星人最近研究了一种操作:求一个字串两个后缀的公共前缀。比方说,有这样一个字符串:madamimadam,我们将这个字符串的各个字符予以标号:序号: 1 2 3 4 5 6 7 8 9 10 11 字符 m a d a m i m a d a m 现在,火星人定义了一个函数LCQ(x, y),表示:该字符串中第x个字符开始的字串,与该字符串中第y个字符开始的字串,两个字串的公共前缀的长度。
6、比方说,LCQ(1, 7) = 5, LCQ(2, 10) = 1, LCQ(4, 7) = 0 在研究LCQ函数的过程中,火星人发现了这样的一个关联:如果把该字符串的所有后缀排好序,就可以很快地求出LCQ函数的值;同样,如果求出了LCQ函数的值,也可以很快地将该字符串的后缀排好序。 尽管火星人聪明地找到了求取LCQ函数的快速算法,但不甘心认输的地球人又给火星人出了个难题:在求取LCQ函数的同时,还可以改变字符串本身。具体地说,可以更改字符串中某一个字符的值,也可以在字符串中的某一个位置插入一个字符。地球人想考验一下,在如此复杂的问题中,火星人是否还能够做到很快地求取LCQ函数的值。字符串长度
7、始终=105,操作数=104 题目是什么意思?一般先化成裸题。LCP是最长公共前缀,现给出一个字符串S,支持以下操作:1 询问 LCP(x,y),也就是原字符串从x开始的字符串和从y开始的字符串最长的公共前缀2 修改,修改原S的一个字符3 添加,在S的第X个字符后面添加一个字符。这个有什么做法?也是可以把问题分开来考虑,比如,怎么快速求LCP?Hash?考虑使用Hash来做实际上这里的LCP(x,y)的x,y所代表的字符串都是S的后缀考虑每一个后缀Suffixi,就是从S的第i个字符开始的后缀,它的Hash值就是Hashi=Si+Si+1*26+Si+2*262.然后Suffixi的某个前缀S
8、i.j的Hash值怎么算?Hash=Hashi-Hashj*26(j-i+1)预处理出所有后缀的Hashi以及26k的话也就是说咱们能够O(1)地求出每一个后缀的某个前缀的Hash值。之前又提到过一点:对于两个相同的字符串,他们的Hash值相同,取模之后也相同。对于两个不同的字符串,他们的Hash值不相同,但取模之后可能相同,模的数越大,同时取不同的模,最后相同的可能性越小。以这两点作为依据,咱们可以这样子做。对于询问后缀X与Y的询问,二分答案,即LCP的长度L,然后O(1)求出这个长度为L的前缀的Hash值,取不同的模,如果不同的模之后都相同,则可认为这两个长度为L的字符串相同,二分答案区间
9、上移,否则则认为不同,二分答案区间下移。这样做的复杂度是O(logS)一次,S为字符串的长度。但是对于修改操作,咱们该怎么做?咱们可以发现,修改了字符Si,那么受到影响的就是它前面的所有字符的Hash值,对于前面来说这个改动比较大而添加字符对于所有的Hash值,都要重算这怎么做啊,这没法做啊实际上还是可以做的咱们以原字符串的顺序建立平衡树,每个节点i维护一个信息,就是它为根的子树所构成的字符串的Hash值和它为根的子树的大小size。那么递推式?Hashfa=Hashlson+sfa*26(Sizelson)+Hashrson*26(Sizelson+1)然后这样子就可以做了每一次把一个后缀全
10、部弄到一棵子树里面,然后它的Hash值就是根节点的那个Hash值。这个得用Splay来做对于修改,直接在子树上修改,然后再往根节点一路走,修改沿途的节点的Hash值。对于添加,直接Splay添加节点,然后往根节点走,每个节点的size+1,Hash值也更新。Splay一次的复杂度是O(logS),所以一次的复杂度是O(logS*logS),假设询问q次,总复杂度就是O(qlogS*logS)P党Splay比较吃力,咱blog有(别人的)AC代码,实在A不了可以去看一看。Hash的实现:2行即可(不算上预处理)上面所提到的Hash能够在O(1)的时间判断两个串是否相同(如果预处理相应的Hash值
11、)。然后Hash不仅仅只可用于字符串,还可以用于某些状态的压缩以及O(1)的查找。比如上一次某道求某个数全部排列模m=0的数的个数的数位dp的,咱们暴力枚举一半的排列a,然后将另一半的排列模m的值转Hash,然后对于排列a,可以计算出为了模m=0另一半所需要的模值,然后O(1)可处理询问。还比如广搜,为了判断某个状态之前是否搜过,也可以设计一个函数做成Hash值。这些都是常见的运用。接着提到的是字符串匹配问题给你一个字符串S,一个字符串P,求P在S中出现了几次。S长度为n,P长度为m。保证m=n咱们所知道的算法1.暴力算法,pos()+delete()以上是检验这题是否是水题的标准2.Rabi
12、n-Karp算法。这是什么鬼?实际上就是刚才讲的Hash咱们对字符串P,可以用刚才X进制的Hash函数,然后对于串P咱们有个Hash函数u,对于S的每个长度为m的子串,计算出一个Hash函数,总共有n-m+1个Hash函数,将它们和P的Hash函数u比较即可。然后计算S的n-m+1个Hash函数可以递推。递推式?(假设字符集大小为x)复杂度?O(n-m+1)。(还可以推广到二维平面的字符串匹配!)这么好的算法,为什么咱们竟然不知道?因为这里的Hash是取模的,取模之后有可能相同,而咱们这里要求的算法是100%正确,也就是说精确匹配,如果P和某个的Hash值不同显然无视,可是如果相同的话还得从头
13、比较。(因为从取模的Hash值不能100%确定某个串一定等于另一个)这样的话最坏n-m+1个都要比较,比较一次O(m),复杂度O(m(n-m+1)。这个算法最坏复杂度和暴力差不多但是期望情况很好。3.有限状态自动机匹配(这个后面ppt会提到,预计下次讲了)这个的复杂度,设字符集大小为,那么复杂度建立字符串P的自动机O(m),匹配O(n)。好处是自动机建立好之后,可以同时求多个串S中是否出现P。4.Knuth-Morris-Pratt算法也就是所说的KMP算法。1)KMP算法的原理?2)KMP算法复杂度的证明?3)能随手敲一个KMP吗?KMP算法其实不难理解。设这里有个S串一部分为ababaab
14、,P串为ababaca,匹配到第六个字符的时候失效,这个时候咱们就想尽量利用已经匹配到的信息。考虑暴力做法是怎么样的。暴力的做法就是右移一位,然后再从头比较,但是咱们通过之前的匹配知道这里是不可能有匹配的。因为已经匹配的部分ababaa的babaa的这个后缀和ababaa这个的公共前缀为0.所以这里还去匹配是不理智的。咱们发现这里的信息所涉及的串好像只跟P有关而这个暴力的过程,实际上就是拿P的第i个后缀和它的前缀继续匹配。而如果这个后缀能够匹配P的某个前缀,那么它就能继续在失配的那个地方匹配下去。实际上就是求P已经匹配的串p1.i的最大后缀,使得它是p1.i的公共前缀!而这个东西是只和P字符串
15、有关比如ababaa字符串,它的p1.5的最大后缀是3.5也就是aba,它和ababaa的前缀p1.3匹配。这个时候咱们直接将P移动到S的ababaa的第二个a处即可。这个时候已经有3个字符被匹配了。所以咱们只要求P的每个前缀的最长的相同后缀就可以了。设这个后缀的长度是nextnexti的含义就是p1.i这个字符串的能够匹配前缀的最大后缀的长度。几个小练习来理解.abbabba的next4=?next6=?next4=1,next6=3.这个next函数理解了之后,考虑nextnext的含义?nexti是p1.i这个字符串能够匹配前缀的最大后缀的长度,也就是说p1.i里面p1.nexti=pi
16、-nexti+1.i而且这个是最长的。那么nextnexti就是p1.nexti这个字符串的能够匹配前缀的最大后缀的长度,又由于p1.nexti=pi-nexti+1.i,所以这个可以理解为:能够匹配p1.nexti前缀的pi-nexti+1.i的最大后缀的长度实际上这个又等价于匹配p1.i前缀的p1.i的第二大后缀。也就是说nextnexti表示的就是能够匹配p1.i的前缀的第二大后缀的长度。那么nextnextnexti?表示的就是能够匹配p1.i的前缀的第三大后缀的长度。以此类推现在考虑求nexti,假设已经知道next1,next2,next3,nexti-1。因为nexti-1表示的是p1.i-1的匹配前缀的最长后缀。那么如果pnexti-1+1=pi的话,那么显然p1.i的匹配的最长前缀就是p1.nexti-1+1了。这个时候nexti=nexti-1+1;如果pnexti-1+1pi。咱们也没关系。nexti表示的是p1.i-1匹配前缀的最长后缀,咱们可以继续去找第二长,第三长后缀继续去匹配。怎么做?之前提到了,假设第K长的后缀的长度是u,那么第K+1长的后缀的长度就是n