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

字符串的相关算法字符串的相关算法还是在前面的话因为本人太弱…所以这几天讲的ppt经常会发现错误，建议在ppt大略的基础上去找相关论文学习。可能重点还是在原理的简单解释…有的地方听不懂的话也没关系，因为每个人没有实现过代码之前实际上都是这样的，可能会对某些地方不理解不影响你对整个算法的印象。以后如果能够专门思考的话也许就会快捷许多。字符串算法有一些的原理看起来比较麻烦，但是代码量往往特别短，所以建议要去完全理解某个算法的原理，这样子以后就算把模板忘了，也许也能够通过原理写出相应的代码。一开始可以学习一下练习模板。字符串算法的模板往往很短，很容易上手。还是在前面的话因为本人太弱…所以这几天讲的ppt经常会发现错大前天提到了分治…提到了这样一个方程…f(n)=f(n/2)+f(n/2)+O(1)这个咱当时是说f(n)=O(nlogn)那是咱SB…TooNaïve考虑线段树的节点，就是这个分布的…可是线段树的节点个数是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，比如大写字母有26个字母，字符集大小为26)然后咱们就有Hash=∑S[i]*X^(i-1)假设字符串长度为s，这个就可以在O(s)的时间内算出来。显然如果存的下最后的Hash值的话，每一个字符串的Hash值必定不相同。Q:为什么？Hash哈希Hash应该都知道…实际上这种计算方法，每个字符串都是X进制下的一个数，而Hash值就是这个X进制的数转十进制的值，由于X进制的数互不相同，显然Hash值，即十进制的数也互不相同。Q：那如果字符串长度过大，以致会爆怎么办？取个模呗…Q：那如果两个字符串不同Hash值取某个模最后相同怎么办？取多个模呗…如果多个模的情况下都相同那么就是同一个字符串。Q：如果取多个模都相同呢？……首先，这个模是你自己定的，所以一般数据是没办法全部卡的。接着，由中国剩余定理，只要取到的每个模足够大，那么最后也可以保证一定范围内的Hash值是一定的。Q：中国剩余定理是什么？以后讲数学的时候会讲吧…顺便可以百度_(:зゝ∠)_实际上这种计算方法，每个字符串都是X进制下的一个数，而Has除了这种Hash以外，字符串Hash也有很多其他的版本，比如ELFhash(黑书上的)据说这个的效果比上面的还好，咱没试过_(:зゝ∠)_FunctionELFhash(vars:string):integer;Varg,h,i:longint;Beginh:=0;fori:=1tolength(s)dobeginh:=hshl4+Ord(S[i]);g:=hand$f0000000($是十六进制)ifg<>0thenh:=hxor(gshr24);h:=hand(notg);end;ELFhash:=hmodM;End;除了这种Hash以外，字符串Hash也有很多其他的版本，比如Bzoj1014JSOI2008火星人火星人最近研究了一种操作：求一个字串两个后缀的公共前缀。比方说，有这样一个字符串：madamimadam，我们将这个字符串的各个字符予以标号：序号：1234567891011

字符madamimadam现在，火星人定义了一个函数LCQ(x,y)，表示：该字符串中第x个字符开始的字串，与该字符串中第y个字符开始的字串，两个字串的公共前缀的长度。比方说，LCQ(1,7)=5,LCQ(2,10)=1,LCQ(4,7)=0在研究LCQ函数的过程中，火星人发现了这样的一个关联：如果把该字符串的所有后缀排好序，就可以很快地求出LCQ函数的值；同样，如果求出了LCQ函数的值，也可以很快地将该字符串的后缀排好序。尽管火星人聪明地找到了求取LCQ函数的快速算法，但不甘心认输的地球人又给火星人出了个难题：在求取LCQ函数的同时，还可以改变字符串本身。具体地说，可以更改字符串中某一个字符的值，也可以在字符串中的某一个位置插入一个字符。地球人想考验一下，在如此复杂的问题中，火星人是否还能够做到很快地求取LCQ函数的值。字符串长度始终<=10^5，操作数<=10^4Bzoj1014JSOI2008火星人火星人最近研究了一题目是什么意思？一般先化成裸题。LCP是最长公共前缀，现给出一个字符串S，支持以下操作：1询问LCP(x,y)，也就是原字符串从x开始的字符串和从y开始的字符串最长的公共前缀2修改，修改原S的一个字符3添加，在S的第X个字符后面添加一个字符。这个有什么做法？题目是什么意思？一般先化成裸题。也是可以把问题分开来考虑，比如，怎么快速求LCP?Hash?考虑使用Hash来做实际上这里的LCP(x,y)的x,y所代表的字符串都是S的后缀考虑每一个后缀Suffix[i]，就是从S的第i个字符开始的后缀，它的Hash值就是Hash[i]=S[i]+S[i+1]*26+S[i+2]*26^2...然后Suffix[i]的某个前缀S[i..j]的Hash值怎么算？Hash=Hash[i]-Hash[j]*26^(j-i+1)预处理出所有后缀的Hash[i]以及26^k的话也就是说咱们能够O(1)地求出每一个后缀的某个前缀的Hash值。也是可以把问题分开来考虑，比如，怎么快速求LCP?之前又提到过一点：对于两个相同的字符串，他们的Hash值相同，取模之后也相同。对于两个不同的字符串，他们的Hash值不相同，但取模之后可能相同，模的数越大，同时取不同的模，最后相同的可能性越小。以这两点作为依据，咱们可以这样子做。对于询问后缀X与Y的询问，二分答案，即LCP的长度L，然后O(1)求出这个长度为L的前缀的Hash值，取不同的模，如果不同的模之后都相同，则可认为这两个长度为L的字符串相同，二分答案区间上移，否则则认为不同，二分答案区间下移。这样做的复杂度是O(logS)一次，S为字符串的长度。之前又提到过一点：但是对于修改操作，咱们该怎么做？咱们可以发现，修改了字符S[i]，那么受到影响的就是它前面的所有字符的Hash值，对于前面来说这个改动比较大…而添加字符…对于所有的Hash值，都要重算…这怎么做啊，这没法做啊…实际上还是可以做的…咱们以原字符串的顺序建立平衡树，每个节点i维护一个信息，就是它为根的子树所构成的字符串的Hash值和它为根的子树的大小size。但是对于修改操作，咱们该怎么做？那么递推式？Hash[fa]=Hash[lson]+s[fa]*26^(Size[lson])+Hash[rson]*26^(Size[lson]+1)然后这样子就可以做了…每一次把一个后缀全部弄到一棵子树里面，然后它的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[fa]=Hash[lson]+s[fa上面所提到的Hash能够在O(1)的时间判断两个串是否相同（如果预处理相应的Hash值）。然后Hash不仅仅只可用于字符串，还可以用于某些状态的压缩以及O(1)的查找。比如上一次某道求某个数全部排列模m=0的数的个数的数位dp的，咱们暴力枚举一半的排列a，然后将另一半的排列模m的值转Hash，然后对于排列a，可以计算出为了模m=0另一半所需要的模值，然后O(1)可处理询问。还比如广搜，为了判断某个状态之前是否搜过，也可以设计一个函数做成Hash值。这些都是常见的运用。上面所提到的Hash能够在O(1)的时间判断两个串是否相同（接着提到的是字符串匹配问题…给你一个字符串S，一个字符串P，求P在S中出现了几次。S长度为n，P长度为m。保证m<=n咱们所知道的算法…1.暴力算法,pos()+delete()…以上是检验这题是否是水题的标准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值不同显然无视，可是如果相同的话还得从头比较。（因为从取模的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吗？3.有限状态自动机匹配（这个后面ppt会提到，预计下次讲了）KMP算法其实不难理解。设这里有个S串一部分为ababaab，P串为ababaca，匹配到第六个字符的时候失效，这个时候咱们就想尽量利用已经匹配到的信息。考虑暴力做法是怎么样的。KMP算法其实不难理解。暴力的做法就是右移一位，然后再从头比较，但是咱们通过之前的匹配知道这里是不可能有匹配的。因为已经匹配的部分ababaa的babaa的这个后缀和ababaa这个的公共前缀为0.所以这里还去匹配是不理智的。字符串的有关算法讲述课件咱们发现这里的信息所涉及的串…好像只跟P有关…而这个暴力的过程，实际上就是拿P的第i个后缀和它的前缀继续匹配。而如果这个后缀能够匹配P的某个前缀，那么它就能继续在失配的那个地方匹配下去。实际上就是求P已经匹配的串p[1..i]的最大后缀，使得它是p[1..i]的公共前缀!而这个东西是只和P字符串有关…比如ababaa字符串，它的p[1..5]的最大后缀是[3..5]也就是aba,它和ababaa的前缀p[1..3]匹配。这个时候咱们直接将P移动到S的ababaa的第二个a处即可。这个时候已经有3个字符被匹配了。咱们发现这里的信息所涉及的串…好像只跟P有关…所以咱们只要求P的每个前缀的最长的相同后缀就可以了。设这个后缀的长度是next[]next[i]的含义就是p[1..i]这个字符串的能够匹配前缀的最大后缀的长度。几个小练习来理解.abbabba的next[4]=?next[6]=?next[4]=1,next[6]=3.这个next[]函数理解了之后，考虑next[next[]]的含义？所以咱们只要求P的每个前缀的最长的相同后缀就可以了。next[i]是p[1..i]这个字符串能够匹配前缀的最大后缀的长度,也就是说p[1..i]里面p[1..next[i]]=p[i-next[i]+1..i]而且这个是最长的。那么next[next[i]]就是p[1..next[i]]这个字符串的能够匹配前缀的最大后缀的长度，又由于p[1..next[i]]=p[i-next[i]+1..i]，所以这个可以理解为：能够匹配p[1..next[i]]前缀的p[i-next[i]+1..i]的最大后缀的长度实际上这个又等价于匹配p[1..i]前缀的p[1..i]的第二大后缀。也就是说next[next[i]]表示的就是能够匹配p[1..i]的前缀的第二大后缀的长度。那么next[next[next[i]]]?表示的就是能够匹配p[1..i]的前缀的第三大后缀的长度。以此类推next[i]是p[1..i]这个字符串能够匹配前缀的最大后现在考虑求next[i]，假设已经知道next[1],next[2],next[3],…next[i-1]。因为next[i-1]表示的是p[1..i-1]的匹配前缀的最长后缀。那么如果p[next[i-1]+1]=p[i]的话，那么显然p[1..i]的匹配的最长前缀就是p[1..next[i-1]+1]了。这个时候next[i]=next[i-1]+1;如果p[next[i-1]+1]<>p[i]。咱们也没关系。next[i]表示的是p[1..i-1]匹配前缀的最长后缀，咱们可以继续去找第二长，第三长后缀…继续去匹配。怎么做？之前提到了，假设第K长的后缀的长度是u，那么第K+1长的后缀的长度就是next[u]枚举第K长后缀，判断其对应前缀+1的字符是不是s[i]，如果是的话，这个就是p[1..i]的匹配的最长前缀了。现在考虑求next[i]，假设已经知道next[1],nex某个实现代码如下：next[1]:=1;Fori:=2tomdoBeginj:=next[i-1];{其实不需要写这句话，因为这个过程倒数第二行已经有了这句话，这里标上是为了强调}while(j>0)and(s[j+1]<>s[i])doj:=next[j];if(s[j+1]=s[i])inc(j);next[i]:=j;End； 代码量也是极短的…某个实现代码如下：以上是预处理。接下来是KMP算法的匹配。实际上比预处理简单多了。假设匹配两个字符，匹配得上，两个都+1，这个显然。考虑匹配不上，假设这个时候是p[1..i]已经匹配,p[i+1]和s[x]失配，咱们只需要沿着next[i]走，然后继续匹配即可，如果走到0了还是没能匹配，那么s[x]无论如何都匹配不了，接下来继续匹配s[x+1]和p[1]。考虑P：abbabbaS：aaababbababbabbaba的匹配过程。以上是预处理。接下来是KMP算法的匹配。实际上比预处理简单多最后就是复杂度证明了…先证明预处理的复杂度是线性的，也就是O(m)的考虑有哪些操作Fori:=2tomdowhile(j>0)and(s[j+1]<>s[i])j=next[j]if(s[j+1]=s[i])inc(j)next[i]=j咱们发现复杂度在于j的变化。考虑j的增加，j最多增加m次，每次都加1。考虑j的减少,由于j最后非负,j减少肯定不超过m，考虑最坏情况j每次只减少1，那么最后也只减少m次，所以复杂度是O(m)线性的。最后就是复杂度证明了…Smartojp1848统计单词数

一般的文本编辑器都有查找单词的功能，该功能可以快速定位特定单词在文章中的位置，有的还能统计出特定单词在文章中出现的次数。现在，请你编程实现这一功能，具体要求是：给定一个单词，请你输出它在给定的文章中出现的次数和第一次出现的位置。!!注意：匹配单词时，不区分大小写，但要求完全匹配，即给定单词必须与文章中的某一独立单词在不区分大小写的情况下完全相同（参见样例1），如果给定单词仅是文章中某一单词的一部分则不算匹配（参见样例2）。输出单词出现的次数和第一次出现的位置(-1代表未出现)单词的位置从0开始Smartojp1848统计单词数

一般的文本编辑器都有ToTotobeornottobeisaquestion20(出现2次，第一次出现在0处）toDidtheOttomanEmpireloseitspoweratthattime-1单词长度<=10文章长度<=10^6To这道题不像普通的匹配，必须要求原文章的对应字符是一个独立的单词。然而这并没有什么…因为咱们可以找出一个单词在原文章出现的所有位置，所以只需要每找到一个，判断他是否是一个独立的单词就可以了。判断是否是独立的单词，其实就是看这个字符串前面和后面是否是空格就可以了…一个独立的单词按照题目意思，必然是前后都是空格…问题解决。这道题不像普通的匹配，必须要求原文章的对应字符是一个独立的单CHHSYOI2015Round2

E.字符串与KMP给你一个n<=10^6的字符串，求该字符串的最小循环节。循环节就是该字符串可由该循环节重复得到。比如abcabc的最小循环节是3，aaaaa的最小循环节是1.要做这道题请加入CH上华师一附中的小组，无需审核。CHHSYOI2015Round2

E.字符串与KMP求一个字符串的循环节…咱们和这道题的标题相联系…很容易想到KMP算法。但是KMP算法不是求字符串P和S的匹配么？这里才一个字符串？考虑next[]的含义，next[i]是p[1..i]的匹配前缀的最大后缀。设字符串P长度为n，那么next[n]含义？P[1..n]的匹配前缀的最大后缀。如果P是由一个最小循环节构成的串，那么咱们能够知道,p[next[n]+1…n]就是它的最小循环节。为什么？假设有K个最小循环节，那么显然P[1..n]的最大后缀就是后K-1个循环节构成的后缀。假设有更长的后缀，可以通过证明最小循环节内部的字符全部右移X位不等于原字符得证。所以算法就是，求这个字符串的next[]，然后答案就是n-next[n];求一个字符串的循环节…咱们和这道题的标题相联系…很容易想到KNoi2014动物园题目大意:给定字符串S，定义num[]，num[i]表示的是S的前缀S[1..i]的能够匹配前缀的后缀的个数，且要求该后缀不能与匹配的前缀相重叠。求∏(1+num[i])S长度n<=10^6一组数据可能有多个(T个)字符串要求该值，T<=10Noi2014动物园题目大意:给定字符串S，定义num[]考虑next[]的含义，next[i]正是S[1..i]匹配前缀的最大后缀，而next[next[i]]就是第二大，以此类推。那么对于每个i，咱们只要找到第一个next[next[..]]，满足next[next[..]]<=i/2，那么这之后的都满足答案。咱们考虑每个i走多少次走到尽头，设这个次数为dist[i]，那么咱们就是要找到一个0<=j<=dist[i],使得它的长度小于等于i/2，显然这是单增的…所以直接二分就可以了，复杂度O(logN)一次。最后的复杂度就是O(nlognT)，可以过。实际上考虑inext[i]看作一条边的话，每个位置看作一个点的话，这显然就是一个森林。所以上面的二分的方法其实就是树上路径的二分。出题者当时愤恨地说，没能卡掉logN真是可惜。这真是一个悲(Xi)伤(Gan)的故事考虑next[]的含义，next[i]正是S[1..i]匹配也就是说这里还有更好的做法？咱们考虑定义一个新的数组Next[]，Next[]数组类似next[]，Next[i]表示S[1..i]中匹配前缀的最大后缀，且这个后缀和前缀不重合。考虑已经求出了Next[1],Next[2]….Next[i-1],现在要求Next[i]，咱们类似next[]的做法，先令j=Next[i-1],然后考虑S[j+1]=S[i]?然后还要判断是否超界，如果超界，贪心的咱们就继续往next[j]走即可。这样的复杂度和Kmp是一样的是O(n)的。Q：为什么不在求next[]的时候一起求Next[]?因为求Next[]的时候如果在求Kmp的时候回去找，实际上就相当于每一次都暴力从某个节点沿着树往根走，这和暴力没啥区别。而后面的类似Kmp的Next[]的求法则是从上一次Next[]作为起点的，可以用类似Kmp复杂度证明的方法证明它也是线性的（这题可见掌握Kmp算法的原理和复杂度的证明有多么重要）也就是说这里还有更好的做法？Smartojp2168

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

Smartojp2168

[Clover9]外星人外星首先看到一道题目要学会转化成裸模型给你一个长度为n的字符串S，和m个字符串P[i],现在从S中截取s[a,b]+s[c,d](1<=a<=b<c<=d<=n)组成一个新的字符串，求所有的截取方案中和m相同的字符串有多少个？栗子：ABCBABA(s)2个Beautifulwords:BAAB，ABBA输出1个，这1个是AB+BA得到的。S长度n<=10^4,m<=100首先看到一道题目要学会转化成裸模型首先容易想到的是暴力法。咱们枚举[a,b][c,d]，然后去比较这个连起来的串和M个串，每一次的复杂度是O(M个串的长度+M*(a,b,c,d)串的长度)。优化的话，甚至可以用Hash做，可以降到O(M)但是这里因为长度太长了，Hash很容易冲突，多次取模也有可能冲突。而即使不冲突，枚举[a,b][c,d]也需要O(n^2)的时间，复杂度O(n^2*m)也会TLE掉…首先容易想到的是暴力法。一种常见的思路就是先想出一个暴力算法，然后思考这种算法哪里慢了，想办法优化它。这里实际上咱们做了很多无用功。咱们枚举S的断点来判断M是否相等，其中不可能是答案的断点太多了，不如反过来思考，咱们可以这样子做。咱们首先可以分开做，每一次只考虑其中一个串P在原S是否可能出现。咱们枚举P的断点，然后对两个断点做Kmp，这样子咱们会发现咱们的答案的状态比原来少了。每一次枚举的复杂度是O(N^2)的。枚举断点的复杂度总的是O(MN^2)的做Kmp，一次O(N)然后M个的话，复杂度就是O(MN^3)的。好像比之前的Hash的方法要好…因为M较小，但是它是一个可以保证正确性的算法…但是貌似还是会TLE？怎么继续优化？哪里还是慢了？一种常见的思路就是先想出一个暴力算法，然后思考这种算法哪里慢容易发现，能够优化的地方就只有枚举断点的O(N^2)了…这里显然太慢了…在这个基础上还要做Kmp，O(n^3)，显然可以优化。咱们用P给S做Kmp，记录下S的每个节点为末端的，能够匹配的最大长度f[i]。咱们发现，如果f[i]>0,f[i]=f[i-1]+1。这样就可以通过f[]得到能够枚举出来的所有前面一截字符串了。但是后面一截怎么处理？断点的后面一截实际上可以这样处理。将P和S都倒过来，然后再做上面的Kmp，求出一个类似的函数g[]那么这个可以得到后面一截的那么只需要找到一个f[i]+g[j]=m且i<j即可。而又由于存在f[i]=m，那么f[i-1]=m-1,…f[i-k]=m-k。g[]类似，那么只需要找到一个f[i]+g[j]>=m，且i<j即可。之前的处理是O(n)没有枚举断点，这里怎么做到也是O(n)?咱们发现，咱们可以枚举j，然后对于每一个g[j]，找之前最大的一个f[i]即可。即对于每一个j，咱们设b[j]表示之前最大的f[i]，这个只要扫一遍就可以O(n)做到，然后枚举g[j]，那么咱们就只要判断b[j]+g[j]>=m是否成立即可，如果成立，那么就存在这样一种断点。这样子做复杂度是O(n)的，而原来的复杂度是O(nm)的。这样最终复杂度就是O(nm)容易发现，能够优化的地方就只有枚举断点的O(N^2)了…这里字符串算法往往代码量少，但是想法有时候难以想出。但一旦想出，基本上后面都很简单，直接上模板，而模板基本上都很短。Timetorelax。字符串算法往往代码量少，但是想法有时候难以想出。接下来提到的是扩展kmp首先是问题：给出一个字符串S(长度为n)和一个字符串P(长度为m)，求字符串S的所有后缀suffix[i]与字符串P的最长公共前缀，其长度记作ex[i]。比如S=aaaaab和P=aaaaaex[1]=5,ex[2]=4,ex[3]=3,ex[4]=2,ex[5]=1,ex[6]=0扩展kmp算法可以在O(n+m)时间求出ex[i]接下来提到的是扩展kmp思想是类似的，假如咱们求出了ex[1],ex[2]….,ex[n-1]，现在要求ex[n]首先[j,j+ex[j]-1]就是从j开头的后缀和P的最大公共前缀。j+ex[j]-1就是这个最大公共前缀的末尾。[j,j+ex[j]-1]同时也是P的长为ex[j]的前缀。设j+ex[j]-1是所有的i+ex[i]-1最大的，也就是右边界最远的。假设n<=j+ex[j]-1.也就是说n所在的字符串在[j,j+ex[j]-1]这个字符串以内。也就是在P的长为ex[j]的前缀里面那么问题其实又是只牵扯到p了。由于这里S[j..j+ex[j]-1]=P[1..ex[j]]而n在[j,j+ex[j]-1]里面则有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]n到最远的边界有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]而咱们要求的是S从n开始有多少长度等于P的前缀，也就是P[n-j+1..ex[j]]与P的前缀的最长公共前缀。思想是类似的，假如咱们求出了ex[1],ex[2]….,ex咱们发现这类似Kmp，最后总会归结为P自己的一个类似的问题。这里最后归结的问题就是，求P的后缀和P的最长公共前缀。不妨设这个的答案数组为next[]假设咱们已经求出所有的next[]，考虑刚才那个问题，已经有S[n..j+ex[j]-1]=P[n-j+1..ex[j]]考虑next[n-j+1]=L那么就有P[1..L]=P[n-j+1..n-j+L]=S[n..n+L-1]如果有n+L-1<=j+ex[j]-1，可以看做n+L<j+ex[j]，那么咱们知道ex[n]就是L，因为之后的根据next[]的定义不可能相同，所以之后不可能还有更长的公共前缀。ex[n]=L如果n+L>=j+ex[j]，那么就要从j+ex[j]即最远边界+1的位置开始和P[j+ex[j]-n]匹配,这里暴力即可。然后更新最大的j+ex[j]-1，如果n+ex[n]-1>j+ex[j]-1则更新。这样就可以求出所有的ex[]了。咱们发现这类似Kmp，最后总会归结为P自己的一个类似的问题。那next[]怎么求？这个实际上就是P和P自己的扩展Kmp类似Kmp的，已知next[1]…next[i-1],求next[i]。咱们发现P和S的扩展kmp的求法可以套用到这里面。而且，这里的next[]是已知的，在计算第n个后缀的next[]，只需要用到之前的next[n-j+1]。这样就完全解决了。考虑复杂度？复杂度的地方在于最远处的移动，而这个移动最多是O(字符串的长度），因此计算next[]和ex[]的复杂度就是O(n+m)，这就是扩展kmp那next[]怎么求？关于代码？因为咱太弱了以前没有写过扩展Kmp，只是理解了，所以不能给出一个保证正确的代码_(:зゝ∠)_扩展kmp的这个匹配过程可能麻烦的是位置，得仔细想一想位置。不过咱没有用过扩展kmp做过题目，题目做得太少见谅…不过多掌握一个算法总比没有好。Timetohaveabreak_(:зゝ∠)_关于代码？最后提一个Manacher算法（马拉车算法）它的用途是用于O(n)求出一个长度为N的字符串以每一个字符为中心的能得到的回文串的长度。首先Manacher算法只能求奇数回文串，因为它每一次都只是枚举其中一个字符作为对称中心。那么偶数回文串怎么办？在每两个相邻字符间添加相同的不属于原字符集的符号即可。比如wshjzaa，处理就是插入“#”，那么就变成了#w#s#h#j#z#a#a#，这里原来的偶数回文串aa就变成了奇数回文串#a#a#这里的处理最多添加O(n)个字符，所以不影响最后复杂度。最后提一个Manacher算法（马拉车算法）Manacher算法定义了这样一个数组p[]，p[i]表示从字符i向左右延伸构成回文串的最大长度。比如刚才的#w#s#h#j#z#a#a#p[]数组该如何表示?这里的p[1]=1,p[2]=2,p[3]=1,p[4]=2,p[5]=1,…….p[13]=3那么还是类似Kmp的那个递推的思想，假设咱们已经知道了p[1],p[2]…p[n-1],现在要求p[n]，如何求？Manacher算法定义了这样一个数组p[]，p[i]表示从类似扩展Kmp，设p[1]~p[n-1]中的所有回文串中右端点最远的是p[i]+i-1，不妨标记为right=p[i]+i-1；那么如果n<right的话，那么显然n在[i,right]间。那么由于[i,right]是回文串的一半，所以它也有对称的另一半[left,i]。而n在另一半也有一个对称点n’而n’的p[]是已经求出来的。如果n+p[n’]-1<=Right的话，那么显然p[n]=p[n’]（假设p[n]>p[n’]，这与n与n’对称的那一部分矛盾了）如果n+p[n’]-1>Right的话，那么就有p[n]=Right-n+1，即n到Right这一段是最长回文串，因为n’所在的回文串能超过Left，对应过来则n所在的回文串不能超过Right，因为假如超过Right的话i的回文串的边界就不是Right了。类似扩展Kmp，设p[1]~p[n-1]中的所有回文串中右端而上面两种情况都是考虑n<=right的情况。实际其实只要写p[n]=min(p[n’],right-n+1)即可。但是n>right的怎么办？没办法…直接按定义来暴力。这个的复杂度？咱们可以发现，right是单调递增向右的，而right向右只有可能是通过暴力这里才能向右，而right最多向右移动O(n)的距离，所以暴力的复杂度是O(n)的。而其余操作的复杂度是O(1)的。所以最终的复杂度就是O(n)的。Manacher算法的思想实际上和扩展Kmp非常相像，都是设置了一个最远的右端点，然后右端点内部的点通过某些性质更新答案，而超出的就暴力更新，由于右端点单调递增，所以暴力的复杂度也就是O(n)的。对了，咱们最后求出的p[]数组是加了#的字符串的，那么原字符串的呢？这里有个式子，新的字符串每一个字符i都对应一个长度为p[i]-1的回文串，这个回文串以该字符为中心（如果这个字符是#的话就是偶数回文串）可见manacher还可以区分偶数和奇数长度的回文串!而上面两种情况都是考虑n<=right的情况。实际其实只要写Hdu3608最长回文给出一个只由小写字母字符a,b,c,…z,组成的字符串S，求S中最长回文串一个测试点有多组测试数据，保证不超过120组，字符串长度<=110000Manacher裸题…直接做建议用C++写…Hdu对P不友善。Hdu3608最长回文给出一个只由小写字母字符a,b,c,Bzoj2160拉拉队训练艾利斯顿商学院篮球队要参加一年一度的市篮球比赛了。拉拉队是篮球比赛的一个看点，好的拉拉队往往能帮助球队增加士气，赢得最终的比赛。所以作为拉拉队队长的楚雨荨同学知道，帮助篮球队训练好拉拉队有多么的重要。拉拉队的选拔工作已经结束，在雨荨和校长的挑选下，n位集优秀的身材、舞技于一体的美女从众多报名的女生中脱颖而出。这些女生将随着篮球队的小伙子们一起，和对手抗衡，为艾利斯顿篮球队加油助威。一个阳光明媚的早晨，雨荨带领拉拉队的队员们开始了排练n个女生从左到右排成一行，每个人手中都举了一个写有26个小写字母中的某一个的牌子，在比赛的时候挥舞，为小伙子们呐喊、加油。雨荨发现，如果连续的一段女生，有奇数个，并且她们手中的牌子所写的字母，从左到右和从右到左读起来一样，那么这一段女生就被称作和谐小群体。现在雨荨想找出所有和谐小群体，并且按照女生的个数降序排序之后，前K个和谐小群体的女生个数的乘积是多少。由于答案可能很大，雨荨只要你告诉她，答案除以19930726的余数是多少就行了。K<=10^12，n<=10^6Bzoj2160拉拉队训练艾利斯顿商学院篮球队要参加一年废话太多…一般都想办法转化到裸模型来。题目大意：给出一个长度为n字符串，把所有以i为中心的奇数长度回文子串按长度降序排序，取前K个，求前K个的长度的乘积。首先…怎么才能只求出奇数长度的回文串？考虑以非#的字符作为中心就可以了。然后只需要把所有的p[]快排一遍，然后从大往小拿即可。复杂度O(nlogn)但是拿的时候…实际上可能有O(n^2)个…直接拿的复杂度可能会达到O(n^2)然而这并不难…咱们可以发现长度为k的答案就是大于等于k的回文串的个数。这个可以对O(n)的p[]使用cnt[]数组计数，cnt[i]表示p[]=i的有多少个，然后从大往小扫,对于长度为i的回文串的个数的答案就是cnt[i+1]+cnt[i+2]…+cnt[n+1]；这个显然从后往前做，就是后缀和，复杂度O(n)然后用快速幂算即可。废话太多…一般都想办法转化到裸模型来。Bzoj2565最长双倍回文串题目大意：给出一个字符串，求最长双倍回文串。双倍回文串就是对于一个串，如果它能划分为X,Y而X,Y都是回文串，那么这个串就是双倍回文串。给出字符串长度2<=n<=10^5举例baacaabbacabb答案是aacaabbacabb，可分解为aacaa和bbacabb。Bzoj2565最长双倍回文串题目大意：给出一个字符串，求Manacher可以搞单个回文串，现在问题是双倍回文串如何搞…考虑咱们已经搞出了p[]数组。双倍回文串就是枚举两个加了#的新字符串的位置i,j(i<j)，满足j-i+1<=p[i]+p[j]，从中间选j-i+1最大的就可以了。这个东西能用平衡树来做….然而以上是一年没做题的咱(嘴巴选手)看到题目的想法…其实上面的方法难写而且复杂度没有下面的好…咱们可以枚举中间的分界点mid（就是#），然后咱们要求的就是回文串能覆盖到mid的最小的j。这个设为min[mid]，类似的还可以设一个从右边覆盖mid的最大的i，设为max[mid]，那么咱们只需要枚举mid,答案就从(max[mid]-min[mid]+1)*2中取最大即可现在问题是min[],max[]怎么求。显然咱们可以发现，min[]是单调递增的。这个的证明蛮容易，设i<j而min[i]>min[j]，可发现取min[j]的回文串也能覆盖到i，而答案更优。利用单调性做就可以了。复杂度O(n)Manacher可以搞单个回文串，现在问题是双倍回文串如何搞加强版：Bzoj2342双倍回文给出一个字符串,求最长双倍回文。看起来和上一题相同？Naive.这里的双倍回文要求，字符串长度能被4整除，字符串是回文串，而该字符串又可以平均分成两半，每一半又是一个回文串。字符串长度N<=5*10^5加强版：Bzoj2342双倍回文给出一个字符串,求最长双倍首先咱们还是知道怎么做单个回文串。问题是这里的双倍回文。先来看看双倍回文的条件,考虑有一个S[i]=#,设其最长回文串的左端点为left=i-p[i]+1,而在[(left+i)/2,i]内有一个j满足j+p[j]-1>=i且S[j]=‘#’，且j尽量地小，由于对称性，显然由于i回文串对称性另外一边也会有一个对称的回文串，这样组成的就是双倍回文。如果直接做…会发现只能暴力…或者这样子…类似上一道题嘴巴选手的做法…求一个满足下列条件的尽量小的jj+p[j]-1>=i,且(left+i)/2<=j而对于这个，咱们发现将j+p[j]-1排好序并且i按从大到小的顺序枚举，那么涉及到的j也就是单调的，然后只需要找这些j里面的最小的j>=(left+i)/2，这个用平衡树可以做。这个的复杂度是O(nlogn+n),C++的SET可以实现首先咱们还是知道怎么做单个回文串。问题是这里的双倍回文。然而pascal却没有set…使用set蒙蔽了大多数选手的双眼…这一题真正精彩的地方不是用set直接水过…这里有一个性质，对于bian=(left+i)/2，原来的j的区间是[bian,i]，可能有许多i和它们对应的left都会计算出一个相同的bian，这是，而对于相同的bian，咱们可以发现，随着i的增长，这个最后的答案j是单调递增的。咱们给每一个bian都存下它最后一次得到的答案。而且如果某个答案j不符合答案，那么咱们可以把边界缩小为[j,i]，然后咱们发现可以用j的答案继续来更新。这是因为随着i的增长最后的答案是单调的，所以之前的那些都可以抛弃。这个有点像…并查集？咱们p党可以用并查集维护这个单调的答案。可是这里面的父亲是固定方向的，因此不能用按秩合并，所以复杂度和平衡树一样是O(nlogn)和原来的平衡树的做法比起来代码显然更短(pascal上)然而pascal却没有set…这道题的单调性可能比较难理解，如果不理解可以去咱的blog看代码，结合代码的话可能更好理解。Manacher算法其实很简单，所以大部分有关题目都不只是Manacher。这时候需要更加大的脑洞（大雾）其实Apio2014好像有提到，所以还是得重视一下马拉车算法Todayisend这道题的单调性可能比较难理解，如果不理解可以去咱的blog看有限状态自动机关于字符串匹配那里提到了用这个来做…自动机就是这样一个东西…它是由五个元素构成的字符集∑一个非空的有限状态集合Q起始状态Start∈Q非空接受状态End∈Q转移函数f()有限状态自动机关于字符串匹配那里提到了用这个来做…自动机的基本工作原理是这样。按顺序读入一个字符串的每一个字符，从起始状态开始，然后根据转移函数f(当前字符，当前状态)算出一个状态，移动到那个状态。当读完所有的字符，如果最后到达的状态是接受状态，那么就认为这个自动机接受这个字符串。否则则认为这个自动机不接受这个字符。所有能被有限状态自动机M接受的串的集合称为M的语言。基本上要理解的就这几个。而这个东西可以用来做匹配。具体可以找JZP的《有限状态自动机》和WC2014的乔明达神犇的《有限状态自动机》来看看。现在举这些里面的两个例子。自动机的基本工作原理是这样。这个自动机是用来做什么的？我们会发现，它只有读入多个0之后读入一个1的话，才可以走到终止状态q2实际上，该自动机的作用就是识别某个串是否有01这个子串。如果有01子串，则该串被自动机接受，否则不接受。字符串的有关算法讲述课件这个是用来做什么的？注意到每次分别读入3个1，就会走到终止状态，也就是说，原串有3的倍数个1的话，就会被接受。这个是用来判断某个串的1的个数是不是3的倍数的自动机。比如111是被接受，01不接受。自动机一旦建好，判断某个串是否具备某个性质，只要在自动机上走一遍就可以了。这也是自动机方便的地方。字符串的有关算法讲述课件于是我们可以考虑使用有限状态自动机来匹配字符串。也就是说，建立字符串T的自动机，使得所有包含T的字符串能够被该自动机接受，而不包含T的字符串则不能被接受。那么问题在于怎么建立这样的自动机？这个说实话已经不需要掌握_(:зゝ∠)_，只是让各位了解一下自动机的一些基本性质就可以了。这个的算法在算法导论的第32章有提到，但复杂度没有Kmp好，预处理为O(n∑)于是我们可以考虑使用有限状态自动机来匹配字符串。其实上面所提到的自动机的概念也是为了引出下面几种和字符串有关的数据结构：AC自动机要聊到AC自动机就得先讲Trie树。Trie树又叫字典树。它的每条边都代表一个字符，它从根节点开始往下走，走到某一个节点，经过的路上的边的字符连成一个字符串S，这个字符串S就是该节点所代表的字符串。显然，根节点代表的字符串就是空串。其实上面所提到的自动机的概念也是为了引出下面几种和字符串有关Trie树一般只要求两个操作，一个是往Trie树里面插入一个字符串，一个是查询Trie树里面是否有某个字符串。插入字符串很简单，按位一个个字符插入就可以了，假设现在走到了节点i，要插入的字符是’a’，那么就先检查节点i的’a’边是否连有儿子j，如果有，就走到j，继续插入下一个字符，如果没有，就新建一个节点j，将节点i的’a’边连向j，然后走到j继续插入下一个字符。而查询只要按位一个个字符走下去就可以了，如果走到某一个节点i，接下来的字符比如是’a’，而若’a’连向了一个儿子j,则走到j，继续重复上面操作，儿子不存在的话，则说明原Trie树没有这个单词，返回。Trie树一般只要求两个操作，一个是往Trie树里面插入一个Trie树的时间复杂度，设插入的字符串的长度为n,则插入的复杂度是O(n)设查询的字符串的长度为n，则查询的复杂度就是O(n)，当然如果Trie树最深深度m<n的话，那么复杂度就是O(m)Trie树实际上有一个很棒的思想，那就是动态开节点，一开始的Trie树只有一个根节点，而每次插入字符串，如果当前走不下去了，就新建一个节点，这样子的话空间复杂度就和插入的字符串的长度有关了。也就是说，对于问题没有涉及到的路，咱们不开设相应的内存，每次问题涉及到一个新的从前没有的路，咱们临时开辟内存。这个思想也可以用于线段树。一开始的线段树只有一个大区间[0,n]，然后每一次涉及到一个区间[p,q]的操作，咱们只临时建立和[p,q]相关的区间的节点。这个思想可以对付一些可能区间[0,10^9]，而实际上涉及到的区间只有10^5等很小的数量级的问题。Trie树的时间复杂度，设插入的字符串的长度为n,则插入的复Poj2418HardwoodSpecies题目大意：给出n个字符串(n<=10^6)，每个字符串长度不超过30，有可能有相同的字符串存在，不同的字符串最多10000种。统计不同种类的字符串出现的次数，并按照字典序排序后输出。比如：ACABA出现了2次，B出现了1次，C出现了一次按照顺序应输出211Poj2418HardwoodSpecies题目大意：我们建立Trie树，每次都插入一个新的字符串。那么怎么统计个数呢？咱们给每一个节点设一个信息域num[],表示该节点所代表的字符串有多少个，然后每次插入一个字符串走到终点，将终点节点的num[]+1然后按字典序走边，遍历一遍就可以了…复杂度？O(输入字符串总长度)空间复杂度也是的。我们建立Trie树，每次都插入一个新的字符串。CFRound#311div2E

AnnandHalf-Palindrome

简要翻译：定义半回文串S，长度为n,就是满足以下条件的字符：对于所有满足以下条件的第i位：1）i为奇数2）i<=(n+1)/23）有S[i]=S[n-i+1]。那么则称该字符串S为半回文串。现给出一个长度为N的字符串S，S的所有子串中是半回文串的按字典序从小到大排成一列，求出第K小的半回文串。这里的字符只有a,b两个N<=5000CFRound#311div2E

AnnandH嗯..看起来问题有两个，怎么求半回文串，以及怎么求第K小的半回文串。首先关于半回文串，manacher什么的算法是做不了了…但是咱们发现咱们好像直接暴力也可以哦…咱们可以这样，枚举一个字符作为中心点(奇数串半回文串)，或者枚举两个字符作为中心点(偶数半回文串)，然后暴力向两边扩展，扩展的复杂度最多是O(n^2)的，这里的n只有5000，显然直接暴力就可以了，没必要想什么麻烦的算法…当然想出更优秀算法的同学就可以出题啦这里的实现可以考虑用f[i][j]表示S[i..j]是不是半回文串，布尔变量存储即可。然后考虑的问题是如何求第K大？嗯..看起来问题有两个，怎么求半回文串，以及怎么求第K小的半咱们可以把所有的可能的半回文串插入一棵Trie，然后对于每一个节点维护一个sum[]表示的是以该节点为根的子树所包含插入的字符串数，然后咱们就可以类似二叉树查找的做了!假设从根节点出发，找第8小的字符串，而a边的儿子连的节点sum[]=6,那么咱们就没必要去a边寻找，答案肯定往b走，以此类推。然后这样子做就可以在O(n)找到答案了。但是!这里咱们要插入的字符串的个数最多有O(n^2)个，每个字符串的长度是O(n)的，复杂度可以达到O(n^3)的插入。………..咱们可以把所有的可能的半回文串插入一棵Trie，然后对于每一算法不优秀的时候，咱们考虑一下这个算法哪里是不是算了重复的东西…显然算了!比如有两个字符串abaa和abaaaaa是半回文串，咱们可以在插入abaa的基础上，插入abaaaaa的剩下的aaa。咱们可以这样子做，每一次都插入S的一个后缀Suffix[p]，然后插入到第i个字符的时候，判断f[p][p+i-1]是不是true，如果是的话那么这个节点就存在一个单词，sum+1，否则继续下去。然后再从下往上递推更新sumSum[fa]=sum[l]+sum[r]+sum[fa];这样子复杂度就还是O(n^2)了。这题就可以A了。算法不优秀的时候，咱们考虑一下这个算法哪里是不是算了重复的东Bzoj2741【Fotile模拟赛】【L】题目大意：主席想要拯救世界，于是他想在线询问区间最大xor和翻译题目：这题是主席出的，给你一个长度为N的数组A，然后每次询问一个区间[l,r]里面的一个最大xor和序列，也就是求出一个i,j使得i<=j,且i,j在[l,r]内，且A[i]xorA[i+1]xorA[i+2]…xorA[j]的值最大。N<=12000,询问数m<=6000强制在线。时限1.5sBzoj2741【Fotile模拟赛】【L】题目大意：主先考虑一个简单版本的做法，求区间[1,n]的最大xor和。这个怎么做？首先要知道两个性质axora=0和0xora=a咱们考虑O(n)求出前缀xor和s[i]S[i]=a[1]xora[2]xor….xora[i]那么区间[i,j]的xor和怎么表示？S[i-1]xorS[j]因为(a[1]xor…xora[i-1])xor(a[1]xor..xora[i-1]xor…xora[j])=a[i]xora[i+1]..xora[j]咱们考虑O(n)求出了前缀xor。咱们枚举右端点j，现在的问题就是，要在0~j-1里面找出一个i使得s[i]xors[j]最大。这个怎么做？先考虑一个简单版本的做法，求区间[1,n]的最大xor和。考虑xor的性质，是按位异或。咱们把S[j]看作一个二进制的01字符串P。那么咱们把S[0]~S[j-1]插入到一棵Trie树里面，然后开始走。如果当前P[k]=0，那么咱们肯定贪心地走Trie树为1的边（如果该边指向的儿子非空）如果当前P[k]=1，那么咱们肯定贪心地走Trie树为0的边（如果该边指向的儿子非空）设最大的数有k位，那么每一次查询的复杂度就是O(k)，查询到S[j]的最大xor值后，把S[j]的二进制插入到Trie里面，然后再去求S[j+1]的。总的复杂度是O(nk)，设最大的数为max，显然就是O(nlogmax)考虑xor的性质，是按位异或。但是上面的做法只能够求[1,n]的，不能够求区间[i,j]的，因为这样子又需要重新处理以i为起点的前缀xor，复杂度是O(n^2logMax)一次，总的复杂度就是O(n^2MlogMax)，n^2m就爆了，logMax可以取几十，肯定T了。这样子好像没有什么好的做法了…考虑这里之所以不能使用Trie树做的原因，正是因为对于区间[i,j]的时候，不能作为答案的[1,i-1]的前缀和字符串也加进来了。考虑这样一个方法，咱们假设同时拥有插入了前i-1个字符串的Trie树，和插入前j个字符串的Trie树，咱们可以通过比对两个Trie树的不同从而得到区间[i,j]的Trie树。然后在区间[i,j]里面咱们又可以用刚才这种方法来做了可是这里的前提是咱们能同时拥有插入前i-1个字符的Trie树和前j的字符的Trie树…也就是所谓的历史版本的Trie树。而这个，就要提到Trie树的可持久化但是上面的做法只能够求[1,n]的，不能够求区间[i,j]的数据结构的可持久化简单意义上讲就是能够保留历史版本的数据结构。也就是说，对于数据结构的每一次有修改的操作，原来的数据结构则是直接修改了做，而对于可持久化的数据结构，它是不能修改的，它的处理办法就是新建节点来存储修改后的数据结构。这样子，咱们就同时拥有修改前和修改后的版本，就可以查询历史某一次修改时候的信息了。比如线段树的可持久化就是一个经典的栗子。考虑一棵线段树。它的区间是[1,4]，现在考虑在[1,3]区间插入线段，按照原来的线段树的做法，是这样的。数据结构的可持久化简单意义上讲就是能够保留历史版本的数据结构字符串的有关算法讲述课件这里把两个区间的未覆盖的状态修改成已经覆盖。这里的修改操作就是直接在原数据结构修改。而可持久化的线段树则是不能在原节点修改。那怎么做？可以这样子做，把原来的线段树复制一份，然后在新的线段树里面做好修改操作。这样子咱们就同时拥有修改前和修改后的线段树了，然后记录下每棵线段树代表的时间段，然后就可以按时间查找了。这里把两个区间的未覆盖的状态修改成已经覆盖。字符串的有关算法讲述课件嗯！咱们已经实现了数据结构的可持久化，但是…时间复杂度？空间复杂度？这样做好像就是暴力…但是好像没有其他的做法了…考虑刚才这种做法，是为什么复杂度高？实际上没必要复制所有的节点…每一次牵涉到的区间以外的节点再复制一次完全是浪费时间和空间。咱们对于没有牵涉到的节点都不复制，还是使用修改前的节点。也就是说这样子做。嗯！咱们已经实现了数据结构的可持久化，但是…这样子做的话就可以节省空间和时间，而且咱们以前也记得，线段树分解区间涉及到的区间是O(logN)的，所以需要建立的节点个数也是O(logN)的，而建立一个节点需要O(1)时间即可，则一次的复杂度就是O(logN)的。而空间复杂度，假设进行了Q次修改，则复杂度就是O(N+QlogN)，而假设再利用Trie树的动态开节点的思想，就可以把空间复杂度变作O(QlogN)这就是线段树的可持久化，而这种线段树就叫作可持久化线段树。以前提到过的主席树实际上是权值线段树的可持久化字符串的有关算法讲述课件而Trie树也可以类似线段树进行可持久化。实际上复杂度是O(logMax)一次，时间和空间复杂度是O(nlogMax)，可以承受。这样子咱们可以类似线段树一样得到所有历史版本的Trie树，然后对于区间询问[i,j]，咱们fork:=i+1tojdo，找到i-1的trie树和k-1的trie树，使用这两个trie树就可以得到[i,k-1]区间的trie树，然后类似的做就可以了。复杂度是O(NMlogMax)，NM=7.2*10^8.看似可以承受…但是logMax可以达到几十…所以最后还是T…而Trie树也可以类似线段树进行可持久化。也就是说可持久化之后还不是正解？这简直在逗人？咱们还能够更快…考虑分块…分块大法好咱们将原来的n个数分成p块，设f[i][j]表示以第i块的开端为起点，后面j个点的区间的最大xor和。这个可以递推:f[i][j]=max(f[i][j-1],[i,j-1]区间以j-1为结尾的字符串的xor和中xora[j]最大的)而后面实际上就是s[i]xors[j-1]xora[j]最大，而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)而对于第二种，咱们直接读答案f[i+1][]就可以了对于第三种，咱们暴力枚举第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自动机是做以下问题的：给你一堆字符串P[i]，和一个字符串S，求P[i]在S中出现了多少次。实际上就是Kmp的升级版本。假设有N个字符串P[i]，设S长度为m,按照Kmp的做法一个个做O(Nm)…看着都觉得不爽…而AC自动机实际上本身就是一棵Trie树，然后类似Kmp的next[]数组，每一个节点都有一个fail指针，它的含义是当前节点所代表的后缀中，能够匹配所有字符串的任意一个的前缀的最大长度。然后求法和next[]类似…失配之后，也是沿着fail往后走…一直走到一个点它有匹配的边，或者最后走到了起点。其实学会了Kmp的话,fail指针的做法是一样的。Trie树相信各位理解得很深了…这里的先将所有的字符串插入到一棵Trie树，然后要将它变成AC自动机只需要加入fail指针。首先Trie树某个节点的深度就是它所代表的字符串的长度，而fail指针指向的必定是深度递减的点。为了保证求某个节点i的fail的时候，它的前继节点fail[j]的fail指针存在，咱们必须使用bfs来求fail指针。从根节点bfs,所有和根节点相连的节点的fail指针初始化为根节点。然后其余的类似kmp的做。咱们到某一个节点i,枚举它能走到的下一个节点j,然后对于j咱们走fail[i],直到相应的字符也能走到一个节点k，那么fail[j]=k，然后把j加入bfs队列即可。复杂度证明？考虑树的每一条路径，都可以看做一个序列的Kmp匹配（因为深度减少），所以复杂度也是线性的。而咱们其实可以进一步优化，咱们给每一个节点配一个go[i]数组，表示输入字符i以后将走到哪个节点，这个可以在bfs的时候一起做，而求出来之后每一次只需要O(1)转移了。虽然是常数级别优化但是有时候很有用。这里的先将所有的字符串插入到一棵Trie树，然后要将它变成A而关于匹配，也是类似Kmp的做法，如果某个地方失配，则从那个地方往回跳，直到能够匹配或者到达根节点。容易知道复杂度也是线性的。接下来看几个问题.而关于匹配，也是类似Kmp的做法，如果某个地方失配，则从那个Poj2778DNASequence给出M（M<=10）个长度不超过10的字符串，问长度为N的不含这些串的字符串的个数mod100000的个数原题最多只有4个字符（A,T,C,G）N<=2000000000（9个0）Poj2778DNASequence给出M（M<=10）肯定不能暴力枚举串，然后对每一个串都Kmp一次判断是否在里面，因为串的长度N太大了，有2*10^9，肯定TLE.考虑对那M个串建立AC自动机，M<=10，长度<=10，AC自动机的节点不超过100。那么咱们发现这个问题就变成了这样，沿着AC自动机走N步（走N步就得到一个长度为N的字符串），途中不经过M个串所代表的节点的路径的条数。有两个问题，一个是如何保证不经过M个串所代表的节点。咱们只要把那些节点删除掉就可以了(无视掉)注意fail