A.CF547E Mike and Friends
多校考过，当时拿根号过的
建立 \(AC\) 自动机，询问转成差分形式，每次把一个字符串的所有前缀位置都 \(+1\), 询问某个点子树内总和
树状数组即可
用广义 \(SAM\) + 线段树合并也可以无脑过
B. Misha and LCP on Tree
匹配两个串好像除了 \(Hash\) 也没啥太好的办法
树剖，每次把字符串的区间按顺序取出，维护正反 \(Hash\) 进行比较即可
C.CF204E Little Elephant and Strings
省选互测5，T2
广义SAM+set维护在哪些串中出现过，然后每个串匹配查询即可
D. AB-Strings
相同的压缩处理，尽量一次操作消去两对，于是分讨开头是否相同，尽量让两串长度相近
E. String Problem
考虑已知 \(i\) 的，求 \(i + 1\) 的答案
首先答案一定是 \(i\) 答案或其 \(border\) 加上新字符构成，自证不难
暴跳 \(border\)， 如果更优则一直跳，否则不跳
不跳是因为随着长度减小，后面的字母一定不增
否则之前就会把较长的替代
F.Suffix Automaton
首先容易定长，然后在后缀树上 \(DFS\) 序就是字典序，每个节点对应的长度都是一个区间，下来扫描线+线段树求第 \(K\) 个位置
G. Substrings in a String
分块，每 \(B\) 个处理一个后缀自动机/KMP啥的，修改暴力重构
对询问进行阈值分治， \(>= B\) 的直接做后缀自动机/KMP \(\frac{n^2}{B}\)
考虑 \(< B\) 的，每个块暴力查询 \(\frac{n^2}{B}\)，块之间暴力查询 \(nB\)
复杂度 \(\frac{n^2}{B} + nB\)
但是，，，，，，，，，，
用 \(bitset\) 可以爆标 \(\frac{n^2}{\omega}\)
H.CF700E Cool Slogans
省选互测3，T1
\(s_{i - 1}\) 为 \(s_{i}\) 的后缀一定不劣，考虑在 \(parent\) 树上 \(DP\)
考虑 \(x\) 的祖先 \(y\)，如果 \(y\) 在 \(x\) 中出现两次，只需要判断 \([pos(x) - len(x) + len(y), pos(x) - 1]\) 中是否存在 \(y\) 即可
使用线段树合并即可快速查询
由于我们只关心\(parent\) 树上父子节点的关系，所以都取到 \(len\) 是可以的
在 \(k\) 相同时，我们希望子串越短越好，所以记录每个答案对应的深度最浅的点，这样每次转移只需要判断一次即可
标签：专题,frac,后缀,len,查询,即可,字符串 From： https://www.cnblogs.com/Chencgy/p/17414267.html