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

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，显然直接暴力就可以了，没必要想什么麻烦的算