oi顶级选手字符串

Techniques向的内容那么就从实际问题来谈一些问题的处理方法，大OI题目中出现过的。来说⋯⋯后缀仙人掌后缀平衡树bordertree什么的你用过么？个人认为在大部分时间里处理字符串问题的主力还是SA/SAM，很少有复杂的字符串算法不依靠SA/SAM就做下去的。上台回答正确的同学之后可以找我(QQ:2641127912)来领一个Steam上的SymphonicRain重置版(112元)。s[lrslr个字符的子串（1开始标号），|s|表示s的长度。当l1时s[lr]简写为sr]sr|s|时s[lr]简写为s[l:]，表示s的一个后缀。ststst的拼接，skks拼起来，特别地，ss以下内容默认大家对KMP/SA/SAMSAMSAM&线段树维护当右端点为r的时候的答案。yuus[yu，那么我们发现维护yu的过程和Link-CutTree中Access的过程是一致的，于是我们每次新加入一个后缀节点的时候只会引起O(logn)段yu的变动。以用这O(logn)段变动来在线段树上维护答案。图:处理到i=2的图示(节点编号是随便标的图:处理到i=1的图示(节点编号是随便标的对于给定的字符串s，O(nlog2n预处理O(logn回答s[lr的本质不同的s[ls[lrs[kkrl，那么应该在线段树上[r,k+r−l)这个区间上+1。那么假设路径(xy)上的点都满足yu=z，且len[par[xalen[y]=b，s[lrs[lr个位置即s，O(nlog2n)预处理O(logn)回答s[lr]的后缀树节点:s[l:r]s[kr](k≥l)先统计前者，注意到加入s[l]时，该后缀节点到根的路径上的每一段yu中，这一段中只有最底下的节点v会有影响，假设v的两个儿子的最早出现位置是s[l:llen[v1]和s[k:klen[v1]，那么在r≥klen[v1的询问中v是一个有两个儿子的节点。s[kr](kls[kr有两个儿子那么它的后缀也有两个儿子。于是我们可以二分s[k:r]，看s[k:r]在后缀树中对应的节点是否满足条件即可。sss某一段的字这一过程，每次询问给出一个询问串p，对于每一个1≤i≤|p|，你需要回答p[:i]在s[l:r]中出现了多少次。只需要三个操作都比暴力快即可(o(|s|))|p|L的询问我们可以暴力处理。因此我们只考虑比较短的询问串。我们维护出每个块断点前后L−1个字符组成的字符串ri=s[posi−L+1:posi+L−2]。可以看出对于比较短的询问串p我们只需要考虑其在ri[L−|p|+1:L+|p|−1]中出现了多少次就行了。于是把所有ri建Trie上SAM。l≤k≤r−|p|+1|k−posi|<|p|Lp≤dfn(s[k:])≤Rp的三维数点（dfsps[k中出现了border(s{si]|sis[|s|i1}，Lborder(s)sborder1p|s|∀1≤i|s|ps[is[ip]p是s(period)PeriodicityLemma:pqspq|s|gcd(pq)gcd(pq)也是sLborder(s|s|/2s|s|Lborder(s的周期。因此s的所有border的下标会形成O(logn)个等差数列。KMP算法可以求出s[1:i]的lbordern=len(s)j=-1Next=foriinwhilej>=0ands[j+1]!=s[i]:j=ifs[j+1]==s[i]:j+=1return给出一个字符串s，O(nlogn)预处理，O(1)回答s[l:r]tmin{s[i:]|l≤i≤r}，可以发现答案一定是t的最短border。于是minsuf(s[lrmin(tminsuf(s[r−m1r]))(m⌊lg(r−l1)⌋)。对每个r,m都预处理即可。maxsuf(s[lrmax(tmaxsuf(s[rm1r]))(m⌊lg(rl1)⌋)，接下来的问题就是怎么求出t。令s[i1:]=max{s[i:]|l≤i≤r}s[i2:]=max{s[i:]|l≤i<i1}，容易看出如果s[i1:]̸t，那么由于s[i1:]是s[i2:]的前缀，s[i2:]是t的前缀因此t有i2−i1的周期。于是只要求最长公共后缀得出周期延伸至何处即可。suf(s{s[i:]|1i|s|}pre(s{si]|1i|s|}定义τ(st)=suf(s)∩pre(t)，给出n个字符串s1s2sn，O(mlogn)预处理O(logn)回答si[k:]是否在τ(si,sj)中。我们只需要找到τ(st)中最长的字符串p1，其余的字符串都是p1的p1的border形成了O(logn找p1可以把所有si的Trie建成SAM把所有si的后缀都放到set里让sj代O(n)预处理O(1)时间内回答s是否在s[:i]s[j:]即回答是否存在x∈border(s[:i])y∈border(s[j:])使得x+y=|s|。x|si]|/2y|s[j:]|/2d是s[:i]的period，故x=i−kd。ks[ikdms[jmi1LCP(ssd]∞)i2LCP(s[1i]s[jm]sd]∞)i1kdi2i1|s|i2kdi1i2O(1)k也容CompressedCompressedPatternsda1da2danp是直接给出的，求p在s中是否出现/出现次数。:LZWcompress:TrieOurOurKMP算法拉过来改一改，我们的流程是：找到失配位置->跳到正确的next位置继续匹配->找到失配位置->...SA/SAM查LCPnextdefgetfail(i,ifs[i+1]==ifj==len(p):returnelse:returni+1,j+1,ifNext[j]<j/2:returngetfail(i,Next[j])#(1l=j-Next[j]j=Next[j]ifs[i+1]!=p[j]:returngetfail(i,l+(j%l))#(2k=j+LCP(s[i+1:],ifk>len(p):returncalcans(i+k-elifk-Next[k]!=returni+k-j-1,k-1,0#(3returngetfail(i+k-j-1,(k-1)%l+l)#(2我们注意到(1),(2)都会把j变为最多原来的2/3O(logmn下面我们考虑(3)部分的复杂度，我们令bi=[nexti≥i/2]，将b序列中从左到右第i段连续的1称为第i层（容易看出来同一层的period是相同的。令第i层的周期为peri，有3|peri|≤|peri+1|。证明：令posi表示第i层最右边的位置，那么显然peri和peri+12Sposi|peri||peri+1|≤posi，那么gcd(|peri||peri+1|)也Sposi]的周期。注意到gcd(|peri||peri+1|)整除|peri+1|，这与peri+1是第i+1层的最短周期矛盾，故我们得到|peri|+|peri+1|>posi。又有2(2)(3)posi≥2|peri|，联立两式可得3|peri|≤|peri+1|留，而层数只有O(logn)层，后退的次数是O(logn)O(logn)是，这个算法只负责判断p是否在s中出现了。l=p[:l]isthelongestprefixofpthatissuffixofs[1]k=2whilek<=r=p[r:]isthelongestsuffixofpthatisaprefixofs[k]checkforanoccuranceofpinp[:l]p[r:]#(1)ifp[:l]s[k]isaprefixofp:l+=len(s[k])k+=b=longestlongborderofp[:l]thatp[:b]s[k]isaprefixofp#(2ifbnotl=longestprefixofpthatissuffixofp[(l+1)//2:l]#(3l=b+s[k]k+=1:pls[k(1pldbkd，我们处理出i1=LCP(p[:l]s[k]p[:d]∞)i2=LCP(pp[:d]∞)则i1kd≤i2。:应该可以用一次KMP处理出来(参见NOI2014动物园CompressedCompressedPatternMatching(Multi母串s是由一个若干个字典串da1da2dan拼接而成的，有m个模板串，是直接给出的，求每个pi是否在s中出现。LZWcompress:字典串是以Trie的形式给出的。P=cur=forkinrange(2,m+1):cur=getprefix(cur,fora,binP:和刚才的做法差不多，getprefix用来在pi的AC自动机里定位curskcheckoccur检查cursk中各个pi的前缀。都翻转过来就是查询getprefix:这个定位工作就是查 +cur的一个最大前缀使得其是某个pcur+k的一个最大后缀使得其是某个i 后缀，那么就是查询sR+curR在pR的Trie上SAM/SAki的问题在SPOJCOT4上出现过，可以用二分hash/在SA上二分进行定位。checkoccurcurskpia中出现的部分pi[:j]，那么就是要求pi[:j]是cur的后缀，pi[j+1:]是sk的前ipiTrieSAMpi[j1对应节点的子树里，这可以看成是一个二O(nlogn)curRpRTrieSAMpij]RBidirectionalBidirectionalSuffixTree(Inenaga,Ukkonen’sAlgorithmUkkonen’sAlgorithm的细节并不广为人知，所以还是简叶节点永远是叶节点，不会随着向后加字符变成非叶节点。而如果s[i:]是叶节点，意味着比s[i:]长的后缀都是叶节点，也就是说非叶节点是某个后缀s[k:]的所有后缀。在向后加字符的时候，我们从s[k:]否需要把这个后缀加到后缀树里。从长到短枚举是用SuffixLink实现的，一个节点的SuffixLink指向它去掉第一个字符后在树中对应节点的位置。MainMainRightExtension:主要问题在向后加字符的时候如何维护后缀自动机的转移LeftExtension:向前加字符的时候可能会把一个叶节点变成非叶节点，需要/p/JPDwhZ37fQ/QAQAspush-back/push-front。每次操作后输出s本质不同的子串数。Source:CTT2018Day3为叶节点的相对大小关系是不会改变的。后缀平衡树是用二分hash的set来实现的因此复杂度是O(nlog2n)（唯一的好处是容易实现一点。请记住，标准的Ukkonen’sAlgorithm会在最后插入终止符$，而这在双向|s[k:]||s|/2s有一个周期串后缀，我们可以利用周期串的性质进行维护一个字符串s，给出询问串的序列ti，支持push-back/push-front/ti在sO(logn)/O(log2由于只有push-front/push-back我们用两个后缀平衡树来维护向前加和向后s0s1ti也维护进平衡树。现在要处查最长的ti[:l0s0[|s0|l11:]和s1[:|t|l11]=ti[l1:]titil0]ti[l1中的出现次数。Lyndonssmin{s[i:]|1i|s|}那么我们称串sLyndonp1p(p1>p2pk)且p1p2pk均为LyndonkAnswerAnswertoSubstringMinimal/MaximalLyndon划分是对这个问题的重要指引。uvuv的最小后缀。定义minsuf(uv)=min{u[i:]v|1≤i≤|u|}minsuf(uv)=min(minsuf(uv)minsuf(v))假设minsuf(uvu[i: