SAM做题记录
题意：求\(S\)的所有出现次数大于1的子串的出现次数乘上长度的最大值。
思路：建出SAM后，预处理出每个节点的子串的出现次数，然后统计答案即可。
题意：求不同子串个数。
思路：考虑到SAM上从根节点到每个节点的路径都是一个子串，因此一遍\(\text{dfs}\)即可。
题意：求一个字符串字典序第\(k\)小的子串。
思路：构建出SAM后，求出每个节点被经过的次数，然后判断\(k\)是否比当前节点能构造的所有子串个数大，再递归下去即可。
题意：给定字符串\(S,T\)，多次询问\(S_l\)到\(S_r\)与\(T\)的最长公共子串的长度。
思路：我们设\(f_i\)表示\(S\)串以\(i\)结尾的子串与\(T\)的最长公共子串长度，这个可以对\(T\)建SAM，然后把\(S\)串跑一遍就可以了。这样答案就是\(\max\limits_{i=l}^r\{\min(f_i,i-l+1)\}\)，但是内层的\(min\)不好处理。我们考虑什么时候\(min\)取到\(f_i\)，即\(f_i\leqslant i-l+1\)，就是\(i-f_i+1\geqslant l\)，这时又有\(i-f_i\)是单增的（\(i\)变大1的时候，\(f_i\)的变化量不超过1），所以我们可以二分找出临界点\(mid\)，那么答案就是\(\max\{i-mid+1,\max\limits_{i=mid}^rf_i\}\)，这个过程可以用ST表做到一只log。
5.P4094 [HEOI2016/TJOI2016]字符串
题意：多次询问\(S[a,b]\)的所有子串和\(S[c,d]\)的\(\text{lcp}\)的最大值。
思路：考虑二分答案，那么这样就变成了求一个子串有没有在另一个区间出现过，然后倍增找到SAM上对应的节点，然后还需维护可持久化线段树判断\([a+mid-1,b]\)里有没有终止接点即可，复杂度\(O(n\log^2n)\)。
题意：多次询问，给出一个字符串\(T\)，求\(T\)有多少个本质不同的子串没有在\([S_l,S_r]\)中出现过。
思路：先考虑\(l=1,r=|S|\)的情况。设\(lim_i\)表示\([T_1,T_i]\)的最长的是\(S\)的子串的后缀长度，\(tag_i\)表示\(T\)的SAM上一个节点的\(endpos\)集合里最小的位置，那么答案就是
\[ans=\sum\limits_{i=2}^{cnt}\max(0,len_i-\max(len_{link_i},lim_{tag_i})) \]然后就考虑如果l,r不固定怎么办。这时需要用可持久化线段树合并维护endpos集合，求\(lim_i\)时，在这SAM上跑到了\(x\)，已经匹配了\([T_{i-len+1},T_i]\)，那么要匹配还得保证后继节点在\([l+len,r]\)之间。复杂度\(O(|S|\log(|S|)+\sum\limits{|T|}\log|S|)\)。
题意：给定\(n\)个字符串，求本质不同字符串数量。
思路：这题关键是建广义SAM，其实就是建完一个串后把lst设为1即可。
题意：给定字符串\(S\)和\(T_1,T_2\cdots T_m\)，多次询问，求\(S[l,r]\)在\(T[L,R]\)的哪个串中出现次数最多，并输出次数。
思路：建出S和T的SAM，然后开可持久化线段树维护每个节点在哪个字符串中出现次数最多，询问时先倍增找到对应节点，然后直接在线段树上查询即可。
标签：子串,题意,SAM,记录,max,做题,字符串,节点 From： https://www.cnblogs.com/Xttttr/p/17263068.html