yybyyb&zjp_shadow的SAM/SA题单

$\sout{P.S.zjp\_shadow}$~~并没有讲，大概是没了。~~ $UPD:$有了有了，但我目前还鸽着。 接着一道一道来。这样刷题对巩固基础很有帮助，可惜之前学数据结构的时候并没有注意，计数与期望又很难这样搞。 # $SAM$ ## $Basic$ ### $[spoj694/705]Distinct\ Substrings$(half half) 不知道$size$的那个结论，被自己菜到了。 比较显然，直接对$SAM$上的每个节点都算一次就可以了。 好像也可以通过拓扑的方式直接遍历$DAWG$，然后反向拓扑统计每个点的拓扑后继子图大小，最后直接输出$siz[0]$就可以了。 ### $[spoj1812]LCS2$(zero half) 网上的做法我都不会正确性，直到一位神秘学长告诉了我一个做法。 建第一个串的$SAM$，之后的串往上面跑的时候，对**第一个串**的每个字符记录一下以它们为开头，匹配到的所有长度的最小值。 最后枚举取个$max$。 貌似跑$SAM$并修改的时候要用个线段树。 ### $[luoguP3804]$【模板】后缀自动机(half half) 不知道$\vert right\vert$的那个结论，被自己菜到了。 如果知道就直接从子树向上统计就可以了。$size$统计也是个套路。 ### $[HAOI2016]$找相同字符（full full） 简单题。 考虑建好一个$SAM$，另一个直接在上面跑。 对于匹配到的任意一个点，它的$parent$树上祖先都可以被匹配。 算出$\vert right\vert$，对于祖先们和刚好匹配的这个点的贡献要分开考虑。祖先可以直接乘上$siz$。注意文本串的次数也要算进去。 ### $[TJOI2015]$弦论（half full） 一开始的想法就是要么走$DAWG$，要么走反串后缀树贪心。均无果，遂弃疗。 感觉自己对$DAWG$理解还不够深。 直接反向拓扑出每个结点之后能走的路径/串数，从小到大枚举字典贪心，若这个儿子之后的路径已经$\ge$当前剩下的路径了就走进去，否则就让剩下的路径数减去这个儿子的路径数，然后继续往其它的儿子贪。 注意此处与$len[x]-len[link[x]]$是没有任何关系的，因为反向拓扑是在$DAWG$统计的，然后一个结点代表的多个串**在字典序上没有任何关系**，因此它们的贡献会分别在不同的$DAWG$转移边上被计算，不用放到一起算。 注意$T=1\vert right\vert$要算到路径数里，$T=0$不用。 ### $[AHOI2013]$差异（full half） 感觉这题$SA$很好做啊$\cdots\cdots$ 前面随便求，重点在$LCP$。 我们直接考虑每个$height$的贡献，往左往右二分出比它小的最近位置，然后它们夹的这个区间里的所有子区间的答案都是它。直接算就做完了。 如果用$SAM$的话，建反串的$SAM$，$parent$树的叶子结点就是反串前缀也就是原串后缀。那么这个结点的贡献次数就不同子树的叶子个数两两相乘，类似铁人两项那个套路。 ### $[luoguP1368]$工艺（full half） ~~其实是因为瞄过DZYO的题解......~~ 直接破环为链，倍增原串建$SAM$就包含了所有情况。 接下来在$SAM$上找一条字典序最小，长度为$\vert S\vert$的路径就可以了，可以直接在$DAWG$上贪心。 ### $[CF235C]Cyclical\ Quest$（half half） 做这种题还不太适应$\cdots\cdots$ 首先，匹配与上题相同，只不过是把询问串倍长然后放进去匹配。 但有些要注意的地方，如果匹配的长度超过了询问串长度，那么得跳$link$到小于为止。以及注意循环可能循环到相同串，答案只会算一次，因此需要给$SAM$上被匹配f的结点打上标记。 ### $[SDOI2016]$生成魔咒（full half） 一开始看错题了，看成动态维护$\vert right\vert$，以为是$LCT$裸题，然后发现只要维护串个数$\cdots\cdots$ 这个东西其实就是$len(cur)-len(link(cur))$，因为你每次加一个字符最多添加$\vert S\vert$个后缀，然后如果之前出现过某个后缀那么这个后缀的后缀也肯定都出现过，那么$\vert right\vert$肯定不一样，那么肯定在$cur$的祖先，把那一部分去掉就可以了。 ## $GSAM/SAM+\#$ ### $[bzoj3277]$串（full half） 建$GSAM$，每次走到建好的点的时候就把$parent$树上次数$+1$。这个过程可以直接在链底打标记，一遍$dfs$统计就可以了。或者也可以$dfs$记一个这个点到根的串个数和，效果是一样的。 网友~~yyb~~给出了$set$启发式合并的高妙在线做法，被gzy神仙分析了它的上界为$O(n\sqrt n\log n)$，不过应该是达不到的。 ### $[CTSC2012]$熟悉的文章（half half） 做过的题，来复习一下$DP$和决策单调性。 首先这题二分答案是很显然的，因为$L0$越大能选串越少，相似度也越低。 我们可以设$dp_i$表示文本串的第$i$位之前能够匹配的最大长度，容易得到$dp$式子: $$dp[i]=\max(dp[i-1],dp[j]+i-j)(j\in[i-maxlen[i],i-mid])$$ ，$maxlen[i]$指的是以第$i$位为结尾的前缀文本串能在字典里匹配的最大长度。这个建好$GSAM$之后可以直接在上面贪心。这样的时间复杂度是$O(n^2\log n)$。 然后可以发现这个$DP$具有决策单调性，因为$i-maxlen[i]$是单调递增的，这个脑补一下匹配情况就可以了解。于是可以把$dp[j]-j$放进单调递减的队列，因为后面的答案如果比前面更优秀，那么前面的答案就没有必要了，然后每次弹掉在$i-maxlen[i]$范围外的答案。这样就可以做到$O(n\log n)$。 ### $[ZJOI2015]$诸神眷顾的幻想乡（half half） ~~读错题了，读成度数是20了。告辞，滚粗。~~ $Trie$上本质不同的子串个数。因为忘了$Trie$上的$SAM$怎么建了所以复习一下。 因为叶子只有20个，可以直接做。建好了之后就是统计$size$的板子了。 ### $[spoj8093]JZPGYZ$（full half） $GSAM$每个节点记一下多少个串可以有这个结点$cnt$。 然后直接往上面跑，直接输出匹配到的节点的$cnt$。 ## $DS+SAM$ ### $[bzoj2555]substring$（half half） 详见$LCT$题单。 ### $[bzoj1396/bzoj2865]$识别子串/字符串识别（half full） 本来以为会做的啊$qwq$不会维护等差数列啊$qwq$ 首先我们可以发现找到每个前缀在$SAM$上的节点，如果它们不是叶子，那对答案肯定没有贡献。如果是叶子，那么它的$minlen-len$这一段区间都可以贡献给答案。 我们假设这个前缀的末节点是$x$，那么，在$x-len+1\to x-minlen(+1)$这一段区间，可以给它们一个长度为$x-i+1$的答案；在$x-minlen+1\to x$这一段区间，可以给它们一个长度为$minlen$的答案。然后我就不会维护等差数列了。 瞄了一眼$yyb$的题解，发现自己日常傻逼了。感觉联赛后复健还没有完成啊，许多套路忘光了。 这个东西可以考虑开两棵线段树分开维护，一棵线段树直接区间赋值，另一棵先赋值$x+1$，最后统一$-i$，就可以处理最小值了。 唉。 ### $[CF666E]Forensic\ Examination$（full half） 想了一下，纯线段树修改不太够，还是线段树合并比较靠谱。 问题就是$\max\{\vert right\vert\}$，先建个$GSAM$，建$GSAM$的过程中给当前结点的线段树上的代表当前串的地方$+1$。 之后在$parent$树上线段树合并。 把询问离线，从左到右推后缀，一直沿着$link$往上，然后在线段树上查$\max$，把答案给对应的询问。 似乎就做完了。感觉好多细节不会实现，要再去看看。 ### $[CF700E]Cool\ Slogans$（half full） 没想到是维护$right$的题啊。自己只想到了第一次选择的最优答案一定是在叶子结点的父亲中选一个，以及可以直接在$SAM$上考虑之后选择的最优方案，然后就一点想法都没有了。 显然，最优方案在$parent$树上一定可以构成它虚树上的一条链，因此我们可以直接考虑从上到下递推，不能从下到上递推是因为一个结点的儿子可能有很多，那么选择可能也有很多，但祖先一定是一条链。 然后遍历到这个点$x$的时候，如果可以让链长度$+1$，那么意味着它上面那个最优方案的最后一个串$S(node=u)$**（不一定是父亲）**在这个串中出现过两次。显然我们需要维护$right$，然后在$S$的线段树上查一段区间内的出现次数，只要$x$的任意一个出现位置的区间$([right(x)-len(x)+1,right(x)])$中串$S$出现过两次，也就是说$S$在$[right(x)-len(x)+len(u),right(x)-1]$出现一次（显然在$right(x)$那个位置也会出现一次），那么就可以直接转移下来。 如果不行，那么就把串$S$保留继续往下，因为显然越保留上面的串答案越优。 然后我就沉浸在如果查$right(x)$的每个位置复杂度是$O(n^2)$的错误思想上沉迷了许久。 然后就发现其实在任意一个$right(x)$的位置上查答案都是一样的。$MDZZ.jpg$ 然后就可以直接做了。 ### $[bzoj3879]SvT$（full half） $yyb$的博客为啥要写算法名称啊$\cdots\cdots$提示太明显了$orz$ 首先发现$LCP$这玩意就是后缀树上的$LCA$，那么建反串$SAM$，然后后缀变为了前缀。 直接找到每个前缀对应的结点，每次询问就建出这些点的虚树，然后贡献就跟$[AHOI2013]$差异差不多，也是叶子两两相乘。 ~~所以题目名字是$\sout{Suffix\ Virtual\ Tree}$对吧？反串$\sout{parent\ tree}$就是后缀树啊~~ ### $[bzoj3413]$匹配（zero half） 想到了一个很复杂的解法，对这两个串建反串$GSAM$然后还是$LCA$，找到对应的结点之后依次直接求。感觉细节很多而且很麻烦。 看了下网上的做法，感觉很有道理。 首先肯定还是对每个位置求$LCP$，那我们可以建好模式串的$SAM$，然后把文本串放上去匹配，首先要维护一下$right$，然后在匹配的那一个结点找到它$right$中的最小值$x$。 然后我们再走一遍原路，就可以对每个点算贡献了。 每个点的贡献大概就是$right\le x$的出现次数乘上它的长度吧。 最后的答案还要加上失配的情况，也就是$x-1$。当然如果模式串根本没有文本串，那$x=n+1$。 ### $[loj6041]$事情的相似度（half full） 详见$LCT$题单。 ### $[hihocoder1413]Rikka\ with\ String$（half half） 此文夹杂看题解前的大概正确做法和看题解后的修改，文章顺序并不是时间顺序。 **** 突发奇想用两个$SAM$可以算出来以$\#$位置原来那个字符为左右端点的变没了的串个数，然后当前跨过$\#$的串可以直接算到答案。然后对于横跨原来那个字符的串就不知道怎么做了。 刚打算看题解，突然想到可以直接算贡献，一开始认为是对每一个$\vert right\vert=1$的串，它对它跨过的位置都有$-1$的贡献，后来（看题解）发现不止是这样，如果某个结点代表的所有出现过的地方都经过了某个位置，那么这些串对这个结点也有贡献。 那么我们需要维护$right_{\min},right_{\max}$，如果这两玩意没相交那肯定没有贡献，否则对相交部分都有$-1$的贡献。由于一个结点代表多个串，所以情况稍微有点复杂。 **** 让我们假设这个结点**有贡献**的最短串长度为$minlen$。 于是又转变为了$+$等差数列的情况，但与$[bzoj1396/bzoj2865]$识别子串/字符串识别不同，它对$right_{\max}-len+1\to right_{\max}-minlen+1$的结点都有$len-minlen+1+right_{\max}-len+1-i$的贡献，对$right_{\max}-minlen+1\to right_{\min}$都有$len-minlen+1$的贡献。 同样，前面那个东西可以另外开一个线段树来更新，但还要记录一下$-i$的次数，最后统一减去$-i\times times$就可以了。 最后答案就是本质不同子串个数-原来横跨这个点的那些串的贡献（在线段树上查）+现在跨过$\#$的串个数（显然是独一无二的）。 这个$minlen$其实就$=right_{\max}-right_{\min}+1$。 **** 网友们好像都是二阶差分？哦对哦，好像不需要线段树维护，这个东西可以用二阶差分直接算，是我傻逼了。 ### $[NOI2015]$品酒大会（full half） 直接建反串$SAM$，然后每个结点对$minlen\to len$的贡献（次数和答案）都是一模一样的，直接线段树区间加和取$Max,Min$。 次数显然就是$\binom{\vert right\vert}{2}$，然后答案的话就是最大值和次大值乘起来，或者最小值和次小值乘起来（负数），可以用线段树合并存一下。 **** 权值最大最小次大次小不用线段树合并，直接转移上来就可以了。$Kelin$给出了一个更简单的做法，不需要数据结构，我是傻逼。 ### $[NOI2018]$你的名字（half full） 我离$Au$差一个$SAM$~~现在不差了，只是把自己的做法$\sout{ban}$成了假做法。那不还是错的吗~~其实就是错的，还假了。 **** $68pts$真实$SAM$练习题，区分掉了我这种不会$SAM$的选手。 想到了一个$O(\vert S\vert q)$的假做法$\cdots\cdots$ 这题需要建两个$SAM$，一个是$S$的$SAM$，一个是$T$的$SAM$。 先来考虑$68pts$怎么做。 我一开始想的做法也是考虑$SAM$上的合法结点，但因为每次在$S$的$SAM$上跑所以复杂度和正确性都是错的。~~明明就差一步了啊啊啊~~ 实际上我们需要考虑对于$T$的每个前缀，找到一个长度$L$使得这个前缀长度不超过$L$的后缀都是$S$的子串。 那么我们先把$T$往$S$上匹配，这样$L$很容易找到。 然后我们再扫一遍$T$的$SAM$，考虑对于每一个结点$x$，我们实际上需要的是$len(x)-\max(len(link(x)),L(rig(x)))$，其中$rig(x)$指的是这个结点的任一出现位置。 考虑$100pts$，实际上就是一个在$S$串上合法出现的问题。 直接上线段树合并维护$right$，然后就找找当前匹配到的这个串最短能不能在$S[l\to r]$里出现，（找到在$[l,r]$最右边那个$right$位置，这个应该可以线段树上二分），然后就跟上面一样了。只要判一下当前结点中的这个串$[l,r]$拥有的长度能不能容纳它出现就可以了。 这题难度没有泳池猛啊。~~flag~~ 好像线段树合并维护$right$然后再找每个$right$的位置来寻找一段区间的答案已经是个套路了。 ### [八省联考$2018$]制胡窜（half half） 这题去重太恶心了$\cdots\cdots$ 首先发现，如果离线的话，计算答案是很好考虑的，我们直接找到$right$的最左边和最右边，然后就会出现一大堆$(i,j)$（最左边那个是$i$的起始点，最右边那个减去长度是$j$的起始点）。 然后我们可以发现，对于中间某些的$right$来说，找它们的满足$i+1,j-1$那个限制的对数是没有必要的，因为这时候找到了的$i,j$其实都是之前已经全部满足的$i,j$。 然后我想到了一个很毒的做法，就是二分找到最左边最右边那两个串包含的相同串的开头/结尾的所有位置的区间（这句话非常玄学，总的来说就是因为我们上面不能舍去所有的中间字符串，要保留那些头/尾进入了最左最右两个串的某些相同串，这些串也有答案要更新），然后我感觉我复杂度就错了$\cdots\cdots$ 看了一下题解，直接反过来求的话去重的问题貌似少很多$\cdots\cdots$正着查貌似需要容斥，感觉挺麻烦。 首先如果反过来求，问题就是三个地方都不出现，也就可以转化为通过割两刀的方式把所有串全部隔开的方案数（**注意断点只有**$n-1$**个**） 然后就比较简单了，两刀一定要把所有的串都割开，我们可以以第一刀割的位置来决定第二刀割的位置。 具体的分类讨论可以去看$\rm shadowice1984$的博客，如果我什么时候~~有闲心~~来写这道题了那就再更新吧。 算贡献好像可以用线段树合并来维护，这样复杂度就对了。 ### $[51nod1600/17E]Simple\ KMP$（zero full） 考场上我失了智，这是道清新题。 首先，我们考虑$f(S)$是啥，因为$KMP$的$fail$是$border$，也就是说当前前缀的父亲是它$border$的位置。那么也就是说，一个前缀的深度可以定义成它$border$的$border$的$\cdots\cdots$，直到$border=\varnothing$，这个$border$的嵌套个数就是它的深度。实际上，我们可以理解成每一个$border^x$都对深度造成了$1$的贡献，因为它们在当前前缀的末尾都出现过一次。那也就是说，$f(S)$**表示每个前缀的出现次数和。** 这是本题最难的部分，想清楚了这个，剩下的就很简单了。 我们考虑如何计算一个串的所有子串的$\sum f(T)$，实际上，我们可以考虑增量，也就是往后加一个字符，所有后缀的$\sum f(T)$。 我们考虑新增的一个后缀$T$与前缀$P$相同，那么这个前缀的出现次数加一。并且可以发现，两个相同子串这样产生了贡献，在下一次新增后缀的时候还要被算贡献，譬如$S\cdots S$，显然在$S\cdots Sa$这个后缀里还有一次贡献。 于是我们先把原来部分的贡献加过来（实际上就是$ans[i-1]$），然后直接去查每个后缀在之前的出现次数，显然查到的答案就是增量。我们再把当前所有后缀的出现次数加一，来回答后面的询问。注意我们每次得到的$ans$是所有后缀的$\sum f$，因此最后还要前缀和一下。 强制在线可以用下$LCT$，但也可以直接建完$SAM$用个树剖维护一下。~~讲道理这题$\sout{LCT}$确实跑得要快一些，明显常数小很多啊~~ 这题培养了一下我对贡献细节的理解能力。 ## $Summary:$ 难题思路还是不清晰，需要提示才能扩展思路； $SAM$性质运用不牢，仍存在细节多算法的出现情况。 # $SA$ ### $[poj2774]Long\ Long\ Message$（zero half） 没想出$SA$。 $SAM:$最长公共子串。 $SA:$把两个串接起来，那么答案一定是某两个后缀的一个$LCP$。 显然一定是某一个$height$，那么对于每个$height(i)$，我们只要看一下$sa(i),sa(i-1)$是否属于两个串，是就可以被算到答案里。 ### $[usaco06DEC]Milk\ Patterns$（half half） 没想出$SA$。想到了一定是一段连续的区间，无果。 $SAM:$找到$\vert right\vert\ge K$的那些点直接统计。 $SA:$首先子串肯定是后缀的前缀，而一个出现了$K$次的子串，它一定在连续排名的$K$个后缀中出现过。 因此我们相当于要找出$\displaystyle\max(\sum_{l=1}^{n-K+2}\min(\sum_{i=l}^{l+K-2}height(i)))$（只要找$K-1$个$height$），这个东西可以维护一个单调递增的队列，每次取队首作为答案，如果枚举的左端点到了队首就把队首弹出，一直取$\max$就可以了。 或者也可以二分答案，然后$O(n)$扫一遍$height$，只要找到一个长度为$K-1$的连续段使得它每个长度都$\ge mid$就可以了。 **** $SA$更多的把子串变为了“后缀的前缀”以方便处理。 ### $[poj1743]Musical\ Theme$（zero half） 没想出$SA$。我真的菜。 $SAM:$直接线段树合并，在$SAM$上每个点找一下$right_{min},right_{max}$间隔是否超过$minlen-len$，取最大的那个计入答案。~~感觉好不优美啊~~ $SA:$还是考虑后缀的前缀相同。还是考虑二分答案，这样可以找到一坨连续的$height\ge mid$的区间。扫的时候记录一下$sa_{max},sa_{min}$，就可以判断是否有不相交子串了。我真的菜。 另外没有看清题面有转调这个要求。事实上虽然可以转调但相邻音符的音高差不会变，可以直接把原段落的相邻音符作差再开始处理。 ### $[POI2000/spoj1812]$公共串/$LCS2$（zero half） 不小心瞄到了一眼~~，之后仍然想了个假做法~~。 事实上就把这些串串起来，中间用分隔符隔开。 然后又双叒叕二分答案，建$SA$的时候记一下这个后缀所属哪个串（主要看首字符位置），然后$height$的时候就看这一段满足要求的连续区间是不是对原来的每个串都有。 ### $[SDOI2008]Sandy$的卡片（full half） 差分之后就是上面那道题。 ### $[NOI2016]$优秀的拆分（zero half） 连$95pts$暴力都不会，只会$85pts$，菜爆了。 我们可以考虑每对相邻点的贡献，也就是统计以这个点为结尾的$AA$串和以这个点为开头的$AA$串，然后相邻位置的贡献就可以乘起来算作答案了。 暴力就可以枚举每个点然后枚举长度，直接用哈希判。 正解其实很暴力，我们既然要枚举长度，那就一起枚举，这样的时间复杂度是$O(n\ln n)$的。我们考虑每个分界点，我们算出相邻分界点的$LCS(uffix),LCP$。然后如果前面那个的$LCP$和后面那个的$LCS$相交（或者相邻）就意味着在一段区间内有答案。那么我们给它们打上差分标记（头尾两种标记分开），然后一遍前缀和统计即可。 ### $[HAOI2016]$找相同字符（half half） 想$SA$想到一半发现假了。 $SAM:$直接放上去匹配，然后就是以每个字符为结尾的最长匹配结点的祖先子串个数都要算入贡献。注意这个点的长度不会到$len$，而是到当前匹配长度。同时因为相同串不同位置要都算所以要维护一下$\vert right\vert$。 $SA:$两串合一中间用分隔符分开，把$height$弄出来。然后按$sa$依次考虑每个串的贡献。 首先答案肯定是两个串各枚举对应后缀的$LCP$产生贡献。 ### $[bzoj2882]$工艺（full half） 破环为链之后好像是$sa(1)$。 ### $[TJOI2016\&HEOI2016]$字符串（zero half） ~~看$yyb$算法知怎么做系列。~~被打脸了，**长度限制对答案有影响**。 我原来想的做法也是主席树找前驱后继，但因为没考虑到长度限制，**直接找前驱后继的答案可能并不是最优的，因为有可能它们相同的部分已经在$b$后面了**。 那么我们为了使前驱后继合法，就得给它的长度做一个限制。 首先问题可以转化为$s[a\cdots b]$的每个后缀与$s[c\cdots d]$的$LCP$最大值。我们二分一个答案$mid$，那么显然在$s[a\cdots b]$的开头应该位于$[a,b-mid+1]$之间。 $SA:$那么这时候我们就是要在$[a,b-mid+1]$之间找$s[c\cdots d]$的前驱后继了。这个可以建一下以$rank$为下标的主席树，找$rank(c)$的前驱后继取$max$即可。 $SAM:$跟上面的思想类似，我们建反串$SAM$，$LCA$就是$LCP$。我们通过倍增找到深度最深的、是$d\to c$所在结点的祖先的、满足它的$minlen\le mid$的结点，这显然是原串$s[c\cdots d]$的一个前缀。然后我们只需要找它的子树有没有一个结点的某个$right$在$[a,b-mid+1]$内就可以了。这个显然是线段树合并可以完成的。 ~~这个用$\sout{SAM}$做不难的啊，怎么我就忘掉了啊~~ ### $[TJOI2017]DNA$（zero half） 我记得在$LCT$里我学过一个半吊子的维护连通性，现在我又学了一个半吊子的$LCP$。我大概是有点问题。 首先这题有一个$NTT$做法，但是我目前早就忘掉了字符串匹配所以告辞。 合并两个串建$SA$然后求$LCP$，直接枚举开头$i$，然后用另外一个指针$x$指向$T[0]$在合并串中的位置，然后直接算$LCP(i,x)$，然后让$i,x$一起跳，显然每跳一次就会有一个字符是不同的，然后略过这个字符继续跳。每跳一次就要$++cnt,cnt>3$就是不合法的。 ### $[JSOI2007]$字符加密（full half） 破环为链，后缀排序，输出第$n$位。 注意只需要输出$sa(i)$在前$n$位的串的第$n$位。 ### $[luoguP5108]$仰望半月的夜空（full half） $SAM:$存一下每个点的$right_{min}$，这个可以直接转移。然后直接扫每个结点，它对$minlen\to len$都有对应的贡献，用个线段树可以随便维护。 $SA:$直接后缀排序，然后用一个指针$p$从$sa(1)$往$sa(n)$扫，从大到小枚举长度$x$，如果$LCP(sa(p),sa(1))=x$就并让当前答案跟$sa(p)$取个$\min$，然后$++p$。因为可能对于$sa(1)$来说，尽管它字典序最小，但某些串可能在某些前面的位置跟它字典序一样。 你可能会想到如果有个串比它短答案可能扩展不过去，但显然这种情况出现是因为这个短串某个位置字典序比前面那个串大了，因此在长度还没有枚举到这个短串的长度的时候这个串不可能被计入答案。 实际上找$LCP$可以直接判这些位的哈希是否相等。 ## $Summary:$ 难题还是没有思路$\cdots\cdots$ **二分答案**是后缀数组最优化问题最常用的套路，务必考虑这个东西。 通常情况下要去考虑某个后缀是否是一段连续串的答案。 务必注意不能想**假算法**。