字符串的有关算法讲述课件

《字符串的有关算法讲述课件》由会员分享，可在线阅读，更多相关《字符串的有关算法讲述课件（98页珍藏版）》请在装配图网上搜索。

1、字符串的相关算法还是在前面的话 因为本人太弱所以这几天讲的ppt经常会发现错误，建议在ppt大略的基础上去找相关论文学习。可能重点还是在原理的简单解释 有的地方听不懂的话也没关系，因为每个人没有实现过代码之前实际上都是这样的，可能会对某些地方不理解不影响你对整个算法的印象。以后如果能够专门思考的话也许就会快捷许多。字符串算法有一些的原理看起来比较麻烦，但是代码量往往特别短，所以建议要去完全理解某个算法的原理，这样子以后就算把模板忘了，也许也能够通过原理写出相应的代码。一开始可以学习一下练习模板。字符串算法的模板往往很短，很容易上手。大前天提到了分治 提到了这样一个方程 f(n)=f(n/2)+

2、f(n/2)+O(1)这个咱当时是说f(n)=O(nlogn)那是咱SB Too Nave 考虑线段树的节点，就是这个分布的 可是线段树的节点个数是O(n)的 这个的解显然应该是f(n)=O(n)在此表示歉意 咱所知道的字符串算法 Pascal的Pos函数 Hash哈希 Kmp和扩展Kmp Trie树 AC自动机 后缀树，后缀数组(SA)，后缀自动机(SAM)Manacher算法 乱搞 最近新出来的：回文自动机(PAM)(太弱不会)。Hash哈希 Hash应该都知道 常用的Hash函数?首先直接把每一个字符的ASCII值加起来作为Hash值不取模的情况很容易冲突 常用的Hash，自己设一个X进

3、制(X=你的字符集的大小-1，比如大写字母有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

5、:=h and$f0000000($是十六进制)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的某个前

8、缀Si.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)的时间判断两个串是否相同（如果预处理相

11、应的Hash值）。然后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()以上是检验这题是否是水题的标

12、准2.Rabin-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串一部分

14、为ababaab，P串为ababaca，匹配到第六个字符的时候失效，这个时候咱们就想尽量利用已经匹配到的信息。考虑暴力做法是怎么样的。暴力的做法就是右移一位，然后再从头比较，但是咱们通过之前的匹配知道这里是不可能有匹配的。因为已经匹配的部分ababaa的babaa的这个后缀和ababaa这个的公共前缀为0.所以这里还去匹配是不理智的。咱们发现这里的信息所涉及的串好像只跟P有关 而这个暴力的过程，实际上就是拿P的第i个后缀和它的前缀继续匹配。而如果这个后缀能够匹配P的某个前缀，那么它就能继续在失配的那个地方匹配下去。实际上就是求P已经匹配的串p1.i的最大后缀，使得它是p1.i的公共前缀!而这个

15、东西是只和P字符串有关 比如ababaa字符串，它的p1.5的最大后缀是3.5也就是aba,它和ababaa的前缀p1.3匹配。这个时候咱们直接将P移动到S的ababaa的第二个a处即可。这个时候已经有3个字符被匹配了。所以咱们只要求P的每个前缀的最长的相同后缀就可以了。设这个后缀的长度是next nexti的含义就是p1.i这个字符串的能够匹配前缀的最大后缀的长度。几个小练习来理解.abbabba的next4=?next6=?next4=1,next6=3.这个next函数理解了之后，考虑nextnext的含义？nexti是p1.i这个字符串能够匹配前缀的最大后缀的长度,也就是说p1.i里面

16、p1.nexti=pi-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-

17、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长的后缀的长度就是nextu 枚举第K长后缀，判断其对应前缀+1的字符是不是si，如果是的话，这个就是p1.i的匹配的最长前缀了。某个实现代码如下：next1:=1;For i:=2 to m

18、 do Begin j:=nexti-1;其实不需要写这句话，因为这个过程倒数第二行已经有了这句话，这里标上是为了强调 while(j0)and(sj+1si)do j:=nextj;if(sj+1=si)inc(j);nexti:=j;End；代码量也是极短的 以上是预处理。接下来是KMP算法的匹配。实际上比预处理简单多了。假设匹配两个字符，匹配得上，两个都+1，这个显然。考虑匹配不上，假设这个时候是p1.i已经匹配,pi+1和sx失配，咱们只需要沿着nexti走，然后继续匹配即可，如果走到0了还是没能匹配，那么sx无论如何都匹配不了，接下来继续匹配sx+1和p1。考虑P：abbabba S

19、：aaababbababbabbaba 的匹配过程。最后就是复杂度证明了 先证明预处理的复杂度是线性的，也就是O(m)的 考虑有哪些操作 For i:=2 to m do while(j0)and(sj+1si)j=nextj if(sj+1=si)inc(j)nexti=j 咱们发现复杂度在于j的变化。考虑j的增加，j最多增加m次，每次都加1。考虑j的减少,由于j最后非负,j减少肯定不超过m，考虑最坏情况j每次只减少1，那么最后也只减少m次，所以复杂度是O(m)线性的。Smartoj p1848 统计单词数 一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还

20、能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。!注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例 1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例 2）。输出单词出现的次数和第一次出现的位置(-1代表未出现)单词的位置从0开始 To To to be or not to be is a question 2 0(出现2次，第一次出现在0处）to Did the Ottoman Empire lose its

21、 power at that time -1 单词长度=10 文章长度=106 这道题不像普通的匹配，必须要求原文章的对应字符是一个独立的单词。然而这并没有什么 因为咱们可以找出一个单词在原文章出现的所有位置，所以只需要每找到一个，判断他是否是一个独立的单词就可以了。判断是否是独立的单词，其实就是看这个字符串前面和后面是否是空格就可以了一个独立的单词按照题目意思，必然是前后都是空格 问题解决。CH HSYOI2015 Round2 E.字符串与KMP 给你一个n=106的字符串，求该字符串的最小循环节。循环节就是该字符串可由该循环节重复得到。比如abcabc的最小循环节是3，aaaaa的最小循

22、环节是1.要做这道题请加入CH上华师一附中的小组，无需审核。求一个字符串的循环节咱们和这道题的标题相联系很容易想到KMP算法。但是KMP算法不是求字符串P和S的匹配么？这里才一个字符串？考虑next的含义，nexti是p1.i的匹配前缀的最大后缀。设字符串P长度为n，那么nextn含义？P1.n的匹配前缀的最大后缀。如果P是由一个最小循环节构成的串，那么咱们能够知道,pnextn+1n就是它的最小循环节。为什么？假设有K个最小循环节，那么显然P1.n的最大后缀就是后K-1个循环节构成的后缀。假设有更长的后缀，可以通过证明最小循环节内部的字符全部右移X位不等于原字符得证。所以算法就是，求这个字符

23、串的next，然后答案就是n-nextn;Noi2014 动物园 题目大意:给定字符串S，定义num，numi表示的是S的前缀S1.i的能够匹配前缀的后缀的个数，且要求该后缀不能与匹配的前缀相重叠。求(1+numi)S长度n=106 一组数据可能有多个(T个)字符串要求该值，T=10 考虑next的含义，nexti正是S1.i匹配前缀的最大后缀，而nextnexti就是第二大，以此类推。那么对于每个i，咱们只要找到第一个nextnext.，满足nextnext.=i/2，那么这之后的都满足答案。咱们考虑每个i走多少次走到尽头，设这个次数为disti，那么咱们就是要找到一个0=j=disti,使

24、得它的长度小于等于i/2，显然这是单增的所以直接二分就可以了，复杂度O(logN)一次。最后的复杂度就是O(nlognT)，可以过。实际上考虑inexti看作一条边的话，每个位置看作一个点的话，这显然就是一个森林。所以上面的二分的方法其实就是树上路径的二分。出题者当时愤恨地说，没能卡掉logN真是可惜。这真是一个悲(Xi)伤(Gan)的故事 也就是说这里还有更好的做法？咱们考虑定义一个新的数组Next，Next数组类似next，Nexti表示S1.i中匹配前缀的最大后缀，且这个后缀和前缀不重合。考虑已经求出了Next1,Next2.Nexti-1,现在要求Nexti，咱们类似next的做法，先

25、令j=Nexti-1,然后考虑Sj+1=Si?然后还要判断是否超界，如果超界，贪心的咱们就继续往nextj走即可。这样的复杂度和Kmp是一样的是O(n)的。Q：为什么不在求next的时候一起求Next?因为求Next的时候如果在求Kmp的时候回去找，实际上就相当于每一次都暴力从某个节点沿着树往根走，这和暴力没啥区别。而后面的类似Kmp的Next的求法则是从上一次Next作为起点的，可以用类似Kmp复杂度证明的方法证明它也是线性的（这题可见掌握Kmp算法的原理和复杂度的证明有多么重要）Smartoj p2168 Clover 9外星人 外星人有n只眼睛，排成一排，从左到右标号为1 to n.他睡

26、觉的时候会给自己带上眼罩，每个眼罩的内侧都有一个大写字母。当他早上起来睁开眼睛时，他想看到beautiful words.外星人还有一个习惯就是，睁眼时他会选择四个数字a,b,c,d,(1=a=b c=d=n)，他将睁开在a=i=b 和c=i=d这个范围内的所有眼睛。设一个beautiful word为字符串s，并且把外星人从左到右看到的字母按顺序拼接成一个字符串串t，如果s和t相同，那么我们认为外星人能够看到s这个beautiful word。你知道他心目中有m个beautiful word。请问在他现在带这个眼罩，任意选择a,b,c,d四个数字的时候，他睁开眼可能看到的beautiful

27、word有多少个？首先看到一道题目要学会转化成裸模型 给你一个长度为n的字符串S，和m个字符串Pi,现在从S中截取sa,b+sc,d(1=a=bc=d=n)组成一个新的字符串，求所有的截取方案中和m相同的字符串有多少个？栗子：ABCBABA(s)2个Beautiful words:BAAB，ABBA 输出1个，这1个是AB+BA得到的。S长度n=104,m0,fi=fi-1+1。这样就可以通过f得到能够枚举出来的所有前面一截字符串了。但是后面一截怎么处理？断点的后面一截实际上可以这样处理。将P和S都倒过来，然后再做上面的Kmp，求出一个类似的函数g那么这个可以得到后面一截的那么只需要找到一个f

28、i+gj=m且i=m，且i=m是否成立即可，如果成立，那么就存在这样一种断点。这样子做复杂度是O(n)的，而原来的复杂度是O(nm)的。这样最终复杂度就是O(nm)字符串算法往往代码量少，但是想法有时候难以想出。但一旦想出，基本上后面都很简单，直接上模板，而模板基本上都很短。Time to relax。接下来提到的是扩展kmp 首先是问题：给出一个字符串S(长度为n)和一个字符串P(长度为m)，求字符串S的所有后缀suffixi与字符串P的最长公共前缀，其长度记作exi。比如 S=aaaaab 和P=aaaaa ex1=5,ex2=4,ex3=3,ex4=2,ex5=1,ex6=0 扩展kmp

29、算法可以在O(n+m)时间求出exi 思想是类似的，假如咱们求出了ex1,ex2.,exn-1，现在要求exn 首先j,j+exj-1就是从j开头的后缀和P的最大公共前缀。j+exj-1就是这个最大公共前缀的末尾。j,j+exj-1同时也是P的长为exj的前缀。设j+exj-1是所有的i+exi-1最大的，也就是右边界最远的。假设n=j+exj-1.也就是说n所在的字符串在j,j+exj-1这个字符串以内。也就是在P的长为exj的前缀里面 那么问题其实又是只牵扯到p了。由于这里Sj.j+exj-1=P1.exj 而n在j,j+exj-1里面 则有Sn.j+exj-1=Pn-j+1.exj n到

30、最远的边界有Sn.j+exj-1=Pn-j+1.exj 而咱们要求的是S从n开始有多少长度等于P的前缀，也就是Pn-j+1.exj与P的前缀的最长公共前缀。咱们发现这类似Kmp，最后总会归结为P自己的一个类似的问题。这里最后归结的问题就是，求P的后缀和P的最长公共前缀。不妨设这个的答案数组为next 假设咱们已经求出所有的next，考虑刚才那个问题，已经有Sn.j+exj-1=Pn-j+1.exj 考虑nextn-j+1=L 那么就有P1.L=Pn-j+1.n-j+L=Sn.n+L-1 如果有n+L-1=j+exj-1，可以看做n+L=j+exj，那么就要从j+exj即最远边界+1的位置开始和

31、Pj+exj-n匹配,这里暴力即可。然后更新最大的j+exj-1，如果n+exn-1j+exj-1则更新。这样就可以求出所有的ex了。那next怎么求？这个实际上就是P和P自己的扩展Kmp 类似Kmp的，已知next1nexti-1,求nexti。咱们发现P和S的扩展kmp的求法可以套用到这里面。而且，这里的next是已知的，在计算第n个后缀的next，只需要用到之前的nextn-j+1。这样就完全解决了。考虑复杂度？复杂度的地方在于最远处的移动，而这个移动最多是O(字符串的长度），因此计算next和ex的复杂度就是O(n+m)，这就是扩展kmp 关于代码？因为咱太弱了以前没有写过扩展Kmp，

32、只是理解了，所以不能给出一个保证正确的代码_(:)_ 扩展kmp的这个匹配过程可能麻烦的是位置，得仔细想一想位置。不过咱没有用过扩展kmp做过题目，题目做得太少见谅 不过多掌握一个算法总比没有好。Time to have a break_(:)_ 最后提一个Manacher算法（马拉车算法）它的用途是用于O(n)求出一个长度为N的字符串以每一个字符为中心的能得到的回文串的长度。首先Manacher算法只能求奇数回文串，因为它每一次都只是枚举其中一个字符作为对称中心。那么偶数回文串怎么办？在每两个相邻字符间添加相同的不属于原字符集的符号即可。比如wshjzaa，处理就是插入“#”，那么就变成了#

33、w#s#h#j#z#a#a#，这里原来的偶数回文串aa就变成了奇数回文串#a#a#这里的处理最多添加O(n)个字符，所以不影响最后复杂度。Manacher算法定义了这样一个数组p，pi表示从字符i向左右延伸构成回文串的最大长度。比如刚才的#w#s#h#j#z#a#a#p数组该如何表示?这里的p1=1,p2=2,p3=1,p4=2,p5=1,.p13=3 那么还是类似Kmp的那个递推的思想，假设咱们已经知道了p1,p2pn-1,现在要求pn，如何求？类似扩展Kmp，设p1pn-1中的所有回文串中右端点最远的是pi+i-1，不妨标记为right=pi+i-1；那么如果nright的话，那么显然n在

34、i,right间。那么由于i,right是回文串的一半，所以它也有对称的另一半left,i。而n在另一半也有一个对称点n 而n的p是已经求出来的。如果n+pn-1pn，这与n与n对称的那一部分矛盾了）如果n+pn-1Right的话，那么就有pn=Right-n+1，即n到Right这一段是最长回文串，因为n所在的回文串能超过Left，对应过来则n所在的回文串不能超过Right，因为假如超过Right的话i的回文串的边界就不是Right了。而上面两种情况都是考虑nright的怎么办？没办法直接按定义来暴力。这个的复杂度？咱们可以发现，right是单调递增向右的，而right向右只有可能是通过暴力

35、这里才能向右，而right最多向右移动O(n)的距离，所以暴力的复杂度是O(n)的。而其余操作的复杂度是O(1)的。所以最终的复杂度就是O(n)的。Manacher算法的思想实际上和扩展Kmp非常相像，都是设置了一个最远的右端点，然后右端点内部的点通过某些性质更新答案，而超出的就暴力更新，由于右端点单调递增，所以暴力的复杂度也就是O(n)的。对了，咱们最后求出的p数组是加了#的字符串的，那么原字符串的呢？这里有个式子，新的字符串每一个字符i都对应一个长度为pi-1的回文串，这个回文串以该字符为中心（如果这个字符是#的话就是偶数回文串）可见manacher还可以区分偶数和奇数长度的回文串!Hdu

36、3608 最长回文 给出一个只由小写字母字符a,b,c,z,组成的字符串S，求S中最长回文串 一个测试点有多组测试数据，保证不超过120组，字符串长度=110000 Manacher裸题直接做 建议用C+写Hdu对P不友善。Bzoj 2160 拉拉队训练 艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起

37、，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练 n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且她们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。K=1012，n=106 废话太多一般都想办法转化到裸模型来。题目大

38、意：给出一个长度为n字符串，把所有以i为中心的奇数长度回文子串按长度降序排序，取前K个，求前K个的长度的乘积。首先怎么才能只求出奇数长度的回文串？考虑以非#的字符作为中心就可以了。然后只需要把所有的p快排一遍，然后从大往小拿即可。复杂度O(nlogn)但是拿的时候实际上可能有O(n2)个 直接拿的复杂度可能会达到O(n2)然而这并不难 咱们可以发现长度为k的答案就是大于等于k的回文串的个数。这个可以对O(n)的p使用cnt数组计数，cnti表示p=i的有多少个，然后从大往小扫,对于长度为i的回文串的个数的答案就是cnti+1+cnti+2+cntn+1；这个显然从后往前做，就是后缀和，复杂度O

39、(n)然后用快速幂算即可。Bzoj2565 最长双倍回文串 题目大意：给出一个字符串，求最长双倍回文串。双倍回文串就是对于一个串，如果它能划分为X,Y而X,Y都是回文串，那么这个串就是双倍回文串。给出字符串长度2=n=105 举例baacaabbacabb 答案是aacaabbacabb，可分解为 aacaa和bbacabb。Manacher可以搞单个回文串，现在问题是双倍回文串如何搞 考虑咱们已经搞出了p数组。双倍回文串就是枚举两个加了#的新字符串的位置i,j(ij)，满足j-i+1=pi+pj，从中间选j-i+1最大的就可以了。这个东西能用平衡树来做.然而以上是一年没做题的咱(嘴巴选手)看

40、到题目的想法 其实上面的方法难写而且复杂度没有下面的好 咱们可以枚举中间的分界点mid（就是#），然后咱们要求的就是回文串能覆盖到mid的最小的j。这个设为minmid，类似的还可以设一个从右边覆盖mid的最大的i，设为maxmid，那么咱们只需要枚举mid,答案就从(maxmid-minmid+1)*2中取最大即可 现在问题是min,max怎么求。显然咱们可以发现，min是单调递增的。这个的证明蛮容易，设iminj，可发现取minj的回文串也能覆盖到i，而答案更优。利用单调性做就可以了。复杂度O(n)加强版：Bzoj2342 双倍回文 给出一个字符串,求最长双倍回文。看起来和上一题相同？Na

41、ive.这里的双倍回文要求，字符串长度能被4整除，字符串是回文串，而该字符串又可以平均分成两半，每一半又是一个回文串。字符串长度N=i且Sj=#，且j尽量地小，由于对称性，显然由于i回文串对称性另外一边也会有一个对称的回文串，这样组成的就是双倍回文。如果直接做会发现只能暴力 或者这样子类似上一道题嘴巴选手的做法求一个满足下列条件的尽量小的j j+pj-1=i,且(left+i)/2=(left+i)/2，这个用平衡树可以做。这个的复杂度是O(nlogn+n),C+的SET可以实现 然而pascal却没有set 使用set蒙蔽了大多数选手的双眼这一题真正精彩的地方不是用set直接水过 这里有一个

42、性质，对于bian=(left+i)/2，原来的j的区间是bian,i，可能有许多i和它们对应的left都会计算出一个相同的bian，这是，而对于相同的bian，咱们可以发现，随着i的增长，这个最后的答案j是单调递增的。咱们给每一个bian都存下它最后一次得到的答案。而且如果某个答案j不符合答案，那么咱们可以把边界缩小为j,i，然后咱们发现可以用j的答案继续来更新。这是因为随着i的增长最后的答案是单调的，所以之前的那些都可以抛弃。这个有点像并查集？咱们p党可以用并查集维护这个单调的答案。可是这里面的父亲是固定方向的，因此不能用按秩合并，所以复杂度和平衡树一样是O(nlogn)和原来的平衡树的做

43、法比起来代码显然更短(pascal上)这道题的单调性可能比较难理解，如果不理解可以去咱的blog看代码，结合代码的话可能更好理解。Manacher算法其实很简单，所以大部分有关题目都不只是Manacher。这时候需要更加大的脑洞（大雾）其实Apio2014好像有提到，所以还是得重视一下马拉车算法 Today is end有限状态自动机 关于字符串匹配那里提到了用这个来做 自动机就是这样一个东西它是由五个元素构成的 字符集 一个非空的有限状态集合Q 起始状态StartQ 非空接受状态EndQ 转移函数f()自动机的基本工作原理是这样。按顺序读入一个字符串的每一个字符，从起始状态开始，然后根据转移

44、函数f(当前字符，当前状态)算出一个状态，移动到那个状态。当读完所有的字符，如果最后到达的状态是接受状态，那么就认为这个自动机接受这个字符串。否则则认为这个自动机不接受这个字符。所有能被有限状态自动机M接受的串的集合称为M的语言。基本上要理解的就这几个。而这个东西可以用来做匹配。具体可以找JZP的有限状态自动机 和WC2014的乔明达神犇的有限状态自动机来看看。现在举这些里面的两个例子。这个自动机是用来做什么的？我们会发现，它只有读入多个0之后读入一个1的话，才可以走到终止状态q2 实际上，该自动机的作用就是识别某个串是否有01这个子串。如果有01子串，则该串被自动机接受，否则不接受。这个是用

45、来做什么的？注意到每次分别读入3个1，就会走到终止状态，也就是说，原串有3的倍数个1的话，就会被接受。这个是用来判断某个串的1的个数是不是3的倍数的自动机。比如111是被接受，01不接受。自动机一旦建好，判断某个串是否具备某个性质，只要在自动机上走一遍就可以了。这也是自动机方便的地方。于是我们可以考虑使用有限状态自动机来匹配字符串。也就是说，建立字符串T的自动机，使得所有包含T的字符串能够被该自动机接受，而不包含T的字符串则不能被接受。那么问题在于怎么建立这样的自动机？这个说实话已经不需要掌握_(:)_，只是让各位了解一下自动机的一些基本性质就可以了。这个的算法在算法导论的第32章有提到，但复

46、杂度没有Kmp好，预处理为O(n)其实上面所提到的自动机的概念也是为了引出下面几种和字符串有关的数据结构：AC自动机 要聊到AC自动机就得先讲Trie树。Trie树又叫字典树。它的每条边都代表一个字符，它从根节点开始往下走，走到某一个节点，经过的路上的边的字符连成一个字符串S，这个字符串S就是该节点所代表的字符串。显然，根节点代表的字符串就是空串。Trie树一般只要求两个操作，一个是往Trie树里面插入一个字符串，一个是查询Trie树里面是否有某个字符串。插入字符串很简单，按位一个个字符插入就可以了，假设现在走到了节点i，要插入的字符是a，那么就先检查节点i的a边是否连有儿子j，如果有，就走到

47、j，继续插入下一个字符，如果没有，就新建一个节点j，将节点i的a边连向j，然后走到j继续插入下一个字符。而查询只要按位一个个字符走下去就可以了，如果走到某一个节点i，接下来的字符比如是a，而若a连向了一个儿子j,则走到j，继续重复上面操作，儿子不存在的话，则说明原Trie树没有这个单词，返回。Trie树的时间复杂度，设插入的字符串的长度为n,则插入的复杂度是O(n)设查询的字符串的长度为n，则查询的复杂度就是O(n)，当然如果Trie树最深深度mn的话，那么复杂度就是O(m)Trie树实际上有一个很棒的思想，那就是动态开节点，一开始的Trie树只有一个根节点，而每次插入字符串，如果当前走不下去

48、了，就新建一个节点，这样子的话空间复杂度就和插入的字符串的长度有关了。也就是说，对于问题没有涉及到的路，咱们不开设相应的内存，每次问题涉及到一个新的从前没有的路，咱们临时开辟内存。这个思想也可以用于线段树。一开始的线段树只有一个大区间0,n，然后每一次涉及到一个区间p,q的操作，咱们只临时建立和p,q相关的区间的节点。这个思想可以对付一些可能区间0,109，而实际上涉及到的区间只有105等很小的数量级的问题。Poj 2418 Hardwood Species 题目大意：给出n个字符串(n=106)，每个字符串长度不超过30，有可能有相同的字符串存在，不同的字符串最多10000种。统计不同种类的

49、字符串出现的次数，并按照字典序排序后输出。比如：A C A B A 出现了2次，B出现了1次，C出现了一次按照顺序应输出 2 1 1 我们建立Trie树，每次都插入一个新的字符串。那么怎么统计个数呢？咱们给每一个节点设一个信息域num,表示该节点所代表的字符串有多少个，然后每次插入一个字符串走到终点，将终点节点的num+1 然后按字典序走边，遍历一遍就可以了 复杂度？O(输入字符串总长度)空间复杂度也是的。CF Round#311 div2 EAnn and Half-Palindrome 简要翻译：定义半回文串S，长度为n,就是满足以下条件的字符：对于所有满足以下条件的第i位：1）i为奇数

50、2）i=(n+1)/2 3）有Si=Sn-i+1。那么则称该字符串S为半回文串。现给出一个长度为N的字符串S，S的所有子串中是半回文串的按字典序从小到大排成一列，求出第K小的半回文串。这里的字符只有a,b两个 N=5000 嗯.看起来问题有两个，怎么求半回文串，以及怎么求第K小的半回文串。首先关于半回文串，manacher什么的算法是做不了了 但是咱们发现咱们好像直接暴力也可以哦 咱们可以这样，枚举一个字符作为中心点(奇数串半回文串)，或者枚举两个字符作为中心点(偶数半回文串)，然后暴力向两边扩展，扩展的复杂度最多是O(n2)的，这里的n只有5000，显然直接暴力就可以了，没必要想什么麻烦的算

51、法 当然想出更优秀算法的同学就可以出题啦 这里的实现可以考虑用fij表示Si.j是不是半回文串，布尔变量存储即可。然后考虑的问题是如何求第K大？咱们可以把所有的可能的半回文串插入一棵Trie，然后对于每一个节点维护一个sum表示的是以该节点为根的子树所包含插入的字符串数，然后咱们就可以类似二叉树查找的做了!假设从根节点出发，找第8小的字符串，而a边的儿子连的节点sum=6,那么咱们就没必要去a边寻找，答案肯定往b走，以此类推。然后这样子做就可以在O(n)找到答案了。但是!这里咱们要插入的字符串的个数最多有O(n2)个，每个字符串的长度是O(n)的，复杂度可以达到O(n3)的插入。.算法不优秀的

52、时候，咱们考虑一下这个算法哪里是不是算了重复的东西 显然算了!比如有两个字符串abaa和abaaaaa是半回文串，咱们可以在插入abaa的基础上，插入abaaaaa的剩下的aaa。咱们可以这样子做，每一次都插入S的一个后缀Suffixp，然后插入到第i个字符的时候，判断fpp+i-1是不是true，如果是的话那么这个节点就存在一个单词，sum+1，否则继续下去。然后再从下往上递推更新sum Sumfa=suml+sumr+sumfa;这样子复杂度就还是O(n2)了。这题就可以A了。Bzoj 2741【Fotile模拟赛】【L】题目大意：主席想要拯救世界，于是他想在线询问区间最大xor和 翻译题

53、目：这题是主席出的，给你一个长度为N的数组A，然后每次询问一个区间l,r里面的一个最大xor和序列，也就是求出一个i,j使得i=j,且i,j在l,r内，且 Ai xor Ai+1 xor Ai+2xor Aj的值最大。N=12000,询问数m=6000 强制在线。时限1.5s 先考虑一个简单版本的做法，求区间1,n的最大xor和。这个怎么做？首先要知道两个性质 a xor a=0和0 xor a=a 咱们考虑O(n)求出前缀xor和si Si=a1xor a2 xor.xor ai 那么区间i,j的xor和怎么表示？Si-1 xor Sj 因为(a1 xorxor ai-1)xor(a1 xo

54、r.xor ai-1 xor xor aj)=ai xor ai+1.xor aj 咱们考虑O(n)求出了前缀xor。咱们枚举右端点j，现在的问题就是，要在0j-1里面找出一个i使得si xor sj最大。这个怎么做？考虑xor的性质，是按位异或。咱们把Sj看作一个二进制的01字符串P。那么咱们把S0Sj-1插入到一棵Trie树里面，然后开始走。如果当前Pk=0，那么咱们肯定贪心地走Trie树为1的边（如果该边指向的儿子非空）如果当前Pk=1，那么咱们肯定贪心地走Trie树为0的边（如果该边指向的儿子非空）设最大的数有k位，那么每一次查询的复杂度就是O(k)，查询到Sj的最大xor值后，把Sj

55、的二进制插入到Trie里面，然后再去求Sj+1的。总的复杂度是O(nk)，设最大的数为max，显然就是O(nlogmax)但是上面的做法只能够求1,n的，不能够求区间i,j的，因为这样子又需要重新处理以i为起点的前缀xor，复杂度是O(n2logMax)一次，总的复杂度就是O(n2MlogMax)，n2m就爆了，logMax可以取几十，肯定T了。这样子好像没有什么好的做法了 考虑这里之所以不能使用Trie树做的原因，正是因为对于区间i,j的时候，不能作为答案的1,i-1的前缀和字符串也加进来了。考虑这样一个方法，咱们假设同时拥有插入了前i-1个字符串的Trie树，和插入前j个字符串的Trie树

56、，咱们可以通过比对两个Trie树的不同从而得到区间i,j的Trie树。然后在区间i,j里面咱们又可以用刚才这种方法来做了 可是这里的前提是咱们能同时拥有插入前i-1个字符的Trie树和前j的字符的Trie树 也就是所谓的历史版本的Trie树。而这个，就要提到Trie树的可持久化 数据结构的可持久化简单意义上讲就是能够保留历史版本的数据结构。也就是说，对于数据结构的每一次有修改的操作，原来的数据结构则是直接修改了做，而对于可持久化的数据结构，它是不能修改的，它的处理办法就是新建节点来存储修改后的数据结构。这样子，咱们就同时拥有修改前和修改后的版本，就可以查询历史某一次修改时候的信息了。比如线段树

57、的可持久化就是一个经典的栗子。考虑一棵线段树。它的区间是1,4，现在考虑在1,3区间插入线段，按照原来的线段树的做法，是这样的。这里把两个区间的未覆盖的状态修改成已经覆盖。这里的修改操作就是直接在原数据结构修改。而可持久化的线段树则是不能在原节点修改。那怎么做？可以这样子做，把原来的线段树复制一份，然后在新的线段树里面做好修改操作。这样子咱们就同时拥有修改前和修改后的线段树了，然后记录下每棵线段树代表的时间段，然后就可以按时间查找了。嗯！咱们已经实现了数据结构的可持久化，但是 时间复杂度？空间复杂度？这样做好像就是暴力 但是好像没有其他的做法了考虑刚才这种做法，是为什么复杂度高？实际上没必要复

58、制所有的节点每一次牵涉到的区间以外的节点再复制一次完全是浪费时间和空间。咱们对于没有牵涉到的节点都不复制，还是使用修改前的节点。也就是说这样子做。这样子做的话就可以节省空间和时间，而且咱们以前也记得，线段树分解区间涉及到的区间是O(logN)的，所以需要建立的节点个数也是O(logN)的，而建立一个节点需要O(1)时间即可，则一次的复杂度就是O(logN)的。而空间复杂度，假设进行了Q次修改，则复杂度就是O(N+QlogN)，而假设再利用Trie树的动态开节点的思想，就可以把空间复杂度变作O(QlogN)这就是线段树的可持久化，而这种线段树就叫作可持久化线段树。以前提到过的主席树实际上是权值线

59、段树的可持久化 而Trie树也可以类似线段树进行可持久化。实际上复杂度是O(logMax)一次，时间和空间复杂度是O(nlogMax)，可以承受。这样子咱们可以类似线段树一样得到所有历史版本的Trie树，然后对于区间询问i,j，咱们for k:=i+1 to j do，找到i-1的trie树和k-1的trie树，使用这两个trie树就可以得到i,k-1区间的trie树，然后类似的做就可以了。复杂度是O(NMlogMax)，NM=7.2*108.看似可以承受但是logMax可以达到几十所以最后还是T也就是说可持久化之后还不是正解？这简直在逗人？咱们还能够更快考虑分块分块大法好咱们将原来的n个数分

60、成p块，设fij表示以第i块的开端为起点，后面j个点的区间的最大xor和。这个可以递推:fij=max(fij-1,i,j-1区间以j-1为结尾的字符串的xor和中xor aj最大的)而后面实际上就是 si xor sj-1 xor aj最大，而i未知。这个在可持久化Trie里面找i-1和j-1的Trie树即可。复杂度是O(N*p*logMax)对于一个询问l,r，咱们找出l在第i块，则答案有可能是只在第i块里面，不在第i块里面，部分在第i块。对于第一种，发现块的大小只有O(N/p)，咱们直接暴力用可持久化Trie就可以做到O(N/plogMax)而对于第二种，咱们直接读答案fi+1就可以了对

61、于第三种，咱们暴力枚举第i块的l后的后缀，然后在第i+1块开端到r的可持久化Trie做就可以了。复杂度O(N/p)可以取p=sqrt(N)，则预处理复杂度是O(Nsqrt(N)logMax)而询问复杂度就是O(Msqrt(N)logMax)，可以过极限数据了。常数较大，注意优化 Trie树相信各位理解得很深了 接下来考虑AC自动机。实际上AC自动机就是在Trie树的基础上来的 AC自动机是做以下问题的：给你一堆字符串Pi，和一个字符串S，求Pi在S中出现了多少次。实际上就是Kmp的升级版本。假设有N个字符串Pi，设S长度为m,按照Kmp的做法一个个做O(Nm)看着都觉得不爽 而AC自动机实际上

62、本身就是一棵Trie树，然后类似Kmp的next数组，每一个节点都有一个fail指针，它的含义是当前节点所代表的后缀中，能够匹配所有字符串的任意一个的前缀的最大长度。然后求法和next类似失配之后，也是沿着fail往后走一直走到一个点它有匹配的边，或者最后走到了起点。其实学会了Kmp的话,fail指针的做法是一样的。这里的先将所有的字符串插入到一棵Trie树，然后要将它变成AC自动机只需要加入fail指针。首先Trie树某个节点的深度就是它所代表的字符串的长度，而fail指针指向的必定是深度递减的点。为了保证求某个节点i的fail的时候，它的前继节点failj的fail指针存在，咱们必须使用b

63、fs来求fail指针。从根节点bfs,所有和根节点相连的节点的fail指针初始化为根节点。然后其余的类似kmp的做。咱们到某一个节点i,枚举它能走到的下一个节点j,然后对于j咱们走faili,直到相应的字符也能走到一个节点k，那么failj=k，然后把j加入bfs队列即可。复杂度证明？考虑树的每一条路径，都可以看做一个序列的Kmp匹配（因为深度减少），所以复杂度也是线性的。而咱们其实可以进一步优化，咱们给每一个节点配一个goi数组，表示输入字符i以后将走到哪个节点，这个可以在bfs的时候一起做，而求出来之后每一次只需要O(1)转移了。虽然是常数级别优化但是有时候很有用。而关于匹配，也是类似Km

64、p的做法，如果某个地方失配，则从那个地方往回跳，直到能够匹配或者到达根节点。容易知道复杂度也是线性的。接下来看几个问题.Poj2778 DNA Sequence 给出M（M=10）个长度不超过10的字符串，问长度为N的不含这些串的字符串的个数 mod 100000的个数 原题最多只有4个字符（A,T,C,G）N=2000000000（9个0）肯定不能暴力枚举串，然后对每一个串都Kmp一次判断是否在里面，因为串的长度N太大了，有2*109，肯定TLE.考虑对那M个串建立AC自动机，M=10，长度=10，AC自动机的节点不超过100。那么咱们发现这个问题就变成了这样，沿着AC自动机走N步（走N步就

65、得到一个长度为N的字符串），途中不经过M个串所代表的节点的路径的条数。有两个问题，一个是如何保证不经过M个串所代表的节点。咱们只要把那些节点删除掉就可以了(无视掉)注意fail指针指向这些节点的节点也要删掉!最后咱们就得到了一张没有这些字符串的AC自动机的图，咱们现在的目标就是这张图上从根走N步，求方案数。而这个昨天有提到过邻接矩阵的做法 将这个图的邻接矩阵自乘N次就是走N步的方案 然后这个就是矩阵快速幂 矩阵大小最多100 x100，复杂度O(1003logN)可见AC自动机不一定只用于匹配，它的路径还可以用来表示含有某些字符串或者不含有某些字符串的字符串。所以在AC自动机路径所做的事情有很

66、多可以出题的机会Bzoj1030 JSOI2007 文本生成器 JSOI交给队员ZYX一个任务，编制一个称之为“文本生成器”的电脑软件：该软件的使用者是一些低幼人群，他们现在使用的是GW文本生成器v6版。该软件可以随机生成一些文章总是生成一篇长度固定且完全随机的文章 也就是说，生成的文章中每个字节都是完全随机的。如果一篇文章中至少包含使用者们了解的一个单词，那么我们说这篇文章是可读的（我们称文章a包含单词b，当且仅当单词b是文章a的子串）。但是，即使按照这样的标准，使用者现在使用的GW文本生成器v6版所生成的文章也是几乎完全不可读的。ZYX需要指出GW文本生成器 v6生成的所有文本中可读文本的数量，以便能够成功获得v7更新版。你能帮助他吗？输入文件的第一行包含两个正整数，分别是使用者了解的单词总数N(=60)，GW文本生成器 v6生成的文本固定长度M；以下N行，每一行包含一个使用者了解的单词。这里所有单词及文本的长度不会超过100，并且只可能包含英文大写字母A.Z。比如 N=2,M=2 A B 则答案为100 其实这个题目就是求长度为N的串，包含M个子串的串的个数。这个还是很麻烦，实际