2023年7月20日发(作者：)

字符串算法总结前⾔标题是骗你进来的，其实⾥⾯全是题⽬。最近⼀直在搞字符串......把⼀些有代表性或者有⼀定难度的题放在这⾥做⼀个总结。[CF666E] Forensic给你⼀个串S以及⼀个字符串数组]]，qq次询问，每次问SS的⼦串S[pl..pr]S[pl..pr]在]]中的哪个串⾥的出现次数最多，并输出出现次数。如有多解输出最靠前的那⼀个。数据范围：|S|,∑|T|,q≤105|S|,∑|T|,q≤105。对]]建⽴⼴义SAMSAM，⽤线段树合并维护出现次数。每次查询先倍增到相应结点，然后直接线段树区间查询。[NOI2011] 阿狸的打字机给定⼀个打字机，有加字符、删字符、打印三种操作。给定操作序列SS，然后有QQ次询问，每次回答第xx次打印的串在第yy次打印的串中出现⼏次。数据范围：|S|,Q≤105|S|,Q≤105⽤栈模拟建出所有打印串的TrieTrie树，然后构建ACAC⾃动机与failfail树。每次询问相当于问xx到TrieTrie的根这条路径上有多少个点能够跳failfail跳到yy。对TrieTrie进⾏dfsdfs，⽤树状数组维护failfail树的⼦树和。[BZOJ3670] 动物园给定⼀个串SS，求每⼀个前缀的不相交borderborder数。 数据范围:|S|≤107|S|≤107。解法⼀：建出failfail树，然后dfsdfs⼀遍failfail树，⽤单调队列维护合法前缀⼤⼩。解法⼆：先预处理出nextnext数组，然后类似nextnext数组的求法求答案，当不合法时跳nextnext数组。[SCOI2013] 密码给定⼀个串的每个回⽂中⼼的扩展⼤⼩，构造满⾜条件的最⼩字典序串。数据范围:n≤105n≤105对这个串跑⼀遍manachermanacher，直接模拟即可，⽤并查集维护两个位置的字符是否相同。最后使⽤最⼩表⽰法求出答案串。[NOI2015] 品酒⼤会给定⼀个串SS，求∑i∑i≠jlcp(sufi,sufj)∑i∑i≠jlcp(sufi,sufj)。数据范围|S|使⽤后缀数组，按照HeightHeight排序后合并后缀，⽤带权并查集维护答案。≤105|S|≤105。或者建出SAMSAM的failfail树后，直接dfsdfs⼀遍failfail树，每次直接合并⼦树答案。[POI2005] SZA-Template求⼀个最短的模板串TT，使得⽤TT对长度为nn的串反复染⾊后可以得到SS。注意：同⼀个位置可以多次染⾊，但只能染⼀种颜⾊。数据范围：n≤5∗105n≤5∗105。显然TT是SS的⼀个borderborder。那么限制条件就是TT在串SS中的出现位置的最⼤间距不能超过|T||T|，其中TT为⼀个borderborder。注意到borderborder匹配的特殊性，当⼀个前缀prepre的borderborder为TT时，TT就在该点匹配上了⼀次。所以跑kmpkmp后建出failfail树。对于⼀个TT，它合法的充要条件为⼦树内的点之间的间距不超过|T||T|，直接⽤setset维护最⼤间距。[BZOJ4310] 跳蚤给⼀个串SS，把它划分为最多KK段，然后挑选出所有段中的最⼤字典序串，再把这些串取最⼤字典序串，称得到的串为TT。最⼩化TT的字典序并输出TT。 数据范围：|S|≤3∗105|S|≤3∗105、K≤20K≤20 。最⼤最⼩化问题，⾸先⼆分TT在SS的所有⼦串中的排名。然后贪⼼验证。由于我们的后缀数组是以后缀排名的，所以从后往前扫。若当前的后缀排名⼩于等于TT，则直接跳过。否则需要考虑割⼀⼑，先求lcplcp，然后查看lcplcp长度范围内是否割了⼀⼑，如果没有就割⼀⼑。最后⽐较割的次数与KK的关系即可。需要实现的功能有快速求lcplcp，给串求排名，给排名求串，这些都可以⽤SASA解决。[HihoCoder1413] Rikka-with-String给⼀个串SS，求把每⼀个位置替换为特殊字符#后本质不同的⼦串个数。数据范围：|S|≤105|S|≤105。先构建SAMSAM，把原串本质不同的⼦串个数求出来，然后考虑变化量。⾸先增加量很显然是i(n−i+1)i(n−i+1) ，考虑求减少量。对于SAMSAM上的每⼀个点，我们维护其最⼤endposendpos与最⼩endposendpos。然后作图可以发现，这个结点对两个区间的贡献分别为 等差数列 和 ⼀个常数。差分即可。[BZOJ2384] Match给定两个排列S,TS,T，要求TT在SS中匹配了多少次。这⾥的匹配定义为：相对⼤⼩相同即算匹配上。数据范围：|S|,|T|≤106|S|,|T|≤106 。空间限制：64MB64MB。魔改⼀下kmpkmp算法。对于TT，我们可以求出⼀个nextnext数组，表⽰失配后到达位置，然后在SS上类似的跑kmpkmp即可。现在的问题变为：求⼀个区间内⼤于某个数的个数，直接想法是主席树，但会MLEMLE。深度发掘⼀下kmpkmp的原理，发现它其实类似⼀个双指针。所以使⽤树状数组，在跳nextnext的时候暴⼒把删除元素在树状数组中删掉。[CF932G] Palindrome给定⼀个偶数长度的串SS，试着把它划分为偶数段。设划分为了kk段，那么需要满⾜si⾸先构建串S′=sk−i+1si=sk−i+1，求⽅案数。数据范围：|S|≤106|S|≤106=s1sns2sn−1...S′=s1sns2sn−1...，问题转化为把S′S′划分为若⼲偶数回⽂串的⽅案数。对于⼀个回⽂串，若它的若⼲回⽂后缀都不超过其长度的⼀半，则这些回⽂后缀⼀定构成等差数列。这样的话，回⽂树上的某个结点的所有祖先最多只会构成loglog个等差数列。我们考虑让同⼀等差数列中的点⼀起转移，维护upup表⽰最浅的⾮等差位置。对于同⼀等差数列中的点，由于其长度不超过原串长度的⼀半，故我们对称后刚好只有upup处的贡献没有加上，所以暴⼒跳等差数列的同时把该贡献加上即可。[NOI2018] 你的名字给定⼀个串SS，有QQ次询问，每次给定⼀个串TT，求不在S[l,r]S[l,r]中出现的TT的⼦串个数。数据范围：|S|,Q,∑|T|≤5∗105|S|,Q,∑|T|≤5∗105，其中l,rl,r也是每次询问给定的变量。对SS建⽴后缀⾃动机，⽤线段树合并得到其endposendpos集合。对于每次询问，先对TT建⽴后缀⾃动机，求的TT的⼦串个数，然后再把在SS中出现的⼦串减掉。对于TT，我们求出其每个前缀的最长匹配后缀limlim。那么对于TT的SAMSAM上的每个点，利⽤limlim把⾮法贡献减掉即可。考虑求limlim，直接把TT放在SS的SAMSAM上做匹配，通过线段树查询endposendpos判断是否出现。fail当失配的时候，不能直接跳failfail，⽽应该要使长度减⼀，然后再次检查。可以发现这个过程中，TT和匹配长度lenlen的关系类似⼀个双指针，所以复杂度是没有问题的。[NOI2016] 优秀的拆分给定⼀个串SS，求所有⼦串划分为AABBAABB形式的⽅案数之和。数据范围：|S|惊现NOINOI史上最良⼼出题⼈，⽩送9595分简直搞笑。考虑最后55分应该怎么拿。显然AABBAABB是⼀个障眼法，我们其实只⽤求AAAA的划分⽅案就⾏了。开始构造，枚举⼀下AA的长度lenlen。然后对于SS，每个长度lenlen我们就设置⼀个顶标点pipi。那么对于任意|A|=len|A|=len的AAAA串，它⼀定恰好经过两个顶标点。所以对于相邻两个顶标点，求⼀下它们的最长公共前、后缀，然后算⼀下贡献即可。[CTSC2010] 珠宝商≤105|S|≤105。给定⼀个串SS和⼀棵nn个结点树，其中树上的每⼀个结点有⼀个字符。求树上每⼀条有序路径构成的字符串在SS中的出现次数之和。数据范围：n,|S|≤50000n,|S|≤50000。树上路径问题考虑点分治，建⽴点分树。由于nn范围⽐较⼩，所以可以数据均摊分治。对于点分⼦树⼤⼩≤−−3−√n≤√n的点，我们直接暴⼒做，复杂度O(√n)=O(n√n)O(√n3)=O(n√n)。−−对于点分⼦树⼤⼩>√n>√n，这类点显然只有√n√n个，我们尝试⽤其它理论解决。考虑得到了两条路径，然后把它们拼接在⼀起。那么对应到字符串上，就是⼀个前缀和⼀个后缀进⾏拼接。所以我们只需要知道每⼀个前缀的⽅案数和每⼀个后缀的⽅案数，然后再乘⼀下就⾏了。我们以求前缀⽅案数为例，后缀⽅案数反过来做即可。观察⼀下匹配过程，我们确定了⼀个endposendpos字符，然后需要向前做匹配。这显然是SAMSAM的DAGDAG和failfail树难以做到的。所以我们需要将SAMSAM⽣成的failfail树进⼀步处理，得到其前缀树，然后匹配就是跳前缀树的⼦树。最后的问题在于如何快速给匹配的点的所有endposendpos加上贡献。回顾⼀下endposendpos集合的得到⽅法，不难发现只需要把这个过程给逆过来就⾏了。我们先在当前点打上标记，全部匹配完后，顺着failfail树把标记向下推送。那么对于⼀个前缀，它在failfail树上对应的结点⼀定是⼀个叶⼦结点，我们直接在该叶⼦查答案。[⼋省联考2018] 制胡窜给定⼀个串SS，有QQ次询问，每次求把串划分为⾮空三段，且三段中⾄少包含⼀个S[pl,pr]S[pl,pr]的⽅案数。数据范围：|S|,|Q|≤100000|S|,|Q|≤100000，其中pl,prpl,pr为每次给定的变量。此题代码细节贼多，如果要写请务必做好代码调试⾄少⼀个晚上的准备。正难则反，考虑求不包含S[pl,pr]S[pl,pr]的⽅案数。为了书写⽅便我们令T=S[pl,pr]T=S[pl,pr]，同时定义TT在SS中的出现次数为nn，定义TT在SS中的出现串为pn，其中lpi,rpilp,rp表⽰它们的左右端点。令mn=p1,mx=pnmn=p1,mx=pn，令len=pr−pl+1len=pr−pl+1。我们现在的⽬标就是⽤两⼑切掉SS中出现的所有TT。⼤⼒讨论：( 1 ) 若存在三个不相交的TT，此时显然⽆解。( 2 ) 否则，若rmn>lmxrmn>lmx，即存在⼀⼑流切法。若第⼀⼑不是⼀⼑流，枚举第⼀⼑切掉了哪些TT，则有：−1n−1Ans=∑ni=1(rpi+1−rpi)(rmn−lpi+1)Ans=∑i=1(rpi+1−rpi)(rmn−lpi+1)ii化简有Ans=−1n−1Ans=(rmn−len+1)∑ni=1(rpi+1−rpi)−∑i=1rpi+1(rpi+1−rpi)若第⼀⼑是⼀⼑流，那么第⼀⼑的落⼑范围为[lmx,rmn][lmx,rmn]，考虑第⼆⼑的位置。rmn−lmx2−1n−1(rmn−len+1)∑ni=1(rpi+1−rpi)−∑i=1rpi+1(rpi+1−rpi)lmx若第⼆⼑也落在[lmx,rmn][lmx,rmn]，这种情况的⽅案数显然为(rmn−)(2)。否则可以发现第⼆⼑落在[lmn,lmx−1)[lmn,lmx−1)的⽅案已经算过了，故只⽤算落在其它位置的⽅案数，这个还是⽐较好算的。若落在右侧，则第⼀⼑落在[lmx,rmn)[lmx,rmn)，第⼆⼑落在[rmn,n][rmn,n]若落在左侧，则第⼀⼑落在(lmx,rmn](lmx,rmn]，第⼆⼑落在[1,lmn][1,lmn]。lmx所以这种情况下的⽅案数为Ans=(rmn−)+(rmn2rmn−lmx2−lmx)(n−len)Ans=()+(rmn−lmx)(n−len) 。( 3 ) 否则，即rmn≤lmxrmn≤lmx，即不存在⼀⼑流切法。顺着上⼀种思路，依旧考虑枚举左边那⼑切掉了哪些TT。那么有：Ans=∑i(rpi+1−rpi)(rmn−lpi+1)Ans=∑i(rp−rp)(rmn−lp) 。i+1ii+1但是由于不存在⼀⼑流，所以⼀定会有⼀个ii被rmnrmn限制，导致切割范围不是完整区间。所以我们把左端点最靠近rmnrmn的那个点先丢掉，设其为ptpt，然后就可以得到⼀个关于ii的限制条件：ri+1>lmxri+1>lmx、li