《字符串的有关算法讲述课件》由会员分享，可在线阅读，更多相关《字符串的有关算法讲述课件（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
