P3426 [POI2005]SZA-Template
考虑 dp，设 \(f(i)\) 表示前 \(i\) 字符所需要的最小印章。
\(f(i)\) 要么等于 \(i\)，要么等于 \(f(nxt(i))\)。
如果存在 \(j\geq n-nxt(i)\)，使得 \(f(j)=f(nxt(i))\)，那么 \(f(i)=f(nxt(i))\)。
P2444 [POI2000]病毒
相当于是要在 AC 自动机上匹配，找到一条不经过 endpos 的环。
需要注意判环和上传 fail 指针的 endpos 的问题。
P2414 [NOI2011] 阿狸的打字机
AC 自动机上 endpos 集合维护这个节点有哪些串。
一次询问 \((x,y)\) 相当于在 AC 自动机走到 \(y\)，对于每个点判断它是否在 \(x\) 的子树内（fail 树上）。
这可以转化为将 \(1\) 到 \(y\) 的路径加 \(1\)（trie 树上），询问 \(x\) 的子树内有多少个点。
也就是说，对于每个 \(y\) 相同的点，加的值都是一样的都是 \(1\) 到 \(y\) 的路径。
因此可以把询问离线下来，对每个相同的 \(y\) 查询不同的 \(x\)。
这可以用树状数组维护一个点到根的链加，每次查询子树和即可。
注意到不同的 \(x\) 或 \(y\) 可能对应相同的节点，因此实际上是对同一节点的所有 \(y\) 处理，需要记录一下每个字符串对应的节点编号。
P2463 [SDOI2008] Sandy 的卡片
相当于是求所有串的最长公共子串的最大值。
不同串直接用不同的标识符隔开，求出 SA。
如果左端点固定，很明显排名区间在包含所有不同子串的情况下越短越好。
因此，开个标记数组双指针一下就行了。
P3181 [HAOI2016]找相同字符
将一个长度为 \(n\) 的串和长度为 \(m\) 的串拼在一起，答案为
\[\sum_{i=1}^{n}\sum_{j=n+1}^{m}lcp(i,j) \]可以计算每个 height 对答案为贡献，拆成差分的形式计算。
P3346 [ZJOI2015]诸神眷顾的幻想乡
读错题了。
读成与一个空地相邻的空地数目不超过 \(20\)。
本来的意思是叶子数目不超过 \(20\)。
那么，对每个叶子，遍历整颗子树，建出广义 SAM，求本质不同的字符串个数即可。
P4081 [USACO17DEC]Standing Out from the Herd P
直接套广义 SAM，再在 fail 树上处理一下就行了。
需要注意的是，SAM 的 fail 树上一个点的儿子的编号不一定大于它，因此不能一个循环解决，还是要建出 fail 树。
P6257 [ICPC2019 WF]First of Her Name
原问题相当于是给定一棵trie树，对于trie上从根到任意节点的一个串，如果它含有某个询问串的反串，那么它对该询问串贡献\(1\)。
可以对询问串建立 AC 自动机，对于每个串，会对 fai 树上到根的路径的所有询问串产生贡献，打一下标记最后 dfs fail 树就行了。
P7046 「MCOI-03」诗韵
先建出 SAM，两个串的最长后缀等于它们在 fail 树上的 LCA 对应的最长串的长度。
考虑计算子串对答案的贡献，它的贡献区间为一段后缀时间。
将修改的串放到 fail 树的对应节点上，某一个子串出现的时间等于子树内最小的大于 \(k\) 的前缀时间。
于是 fail 树上线段树合并，查询的时候线段树二分即可。
P2178 [NOI2015] 品酒大会
求有多少对 \(i\neq j\) 满足 \(lcp(i,j)\geq r\)，且求 \(\max(a_i+a_j)\)，对所有 \(r\in[0,n-1]\)。
考虑每个 height 的贡献，算出贡献区间，差分一下即可算出询问 1。
对于询问 2，只需要维护一个排名区间的 st 表，存最大值和最小值，对每个 height 查询一下就行了。
CF954I Yet Another String Matching Problem
注意到字符集很小，因此可以暴力枚举那些字符并在一起。
每次检验跑一次 KMP 匹配即可。
CF1073G Yet Another LCP Problem
建出后缀树，问题转化为求
\[\sum_i\sum_jdepth(lca(a_i,b_j)) \]可以转化为对所有 \(a_i\)，对它到根节点的路径加上对应的权值，对每个 \(b_j\) 查询它到根的路径和，使用 LCT 维护。
CF547E Mike and Friends
先对原串建立 AC 自动机。
将询问差分，把每个串依次加入树状数组中。
对于差分后的询问，相当于是询问子树的权值和。
P4156 [WC2016]论战捆竹竿
每次增加的长度只可能是 \(n-border\)，因此可以考虑使用 KMP 预处理出所有 \(border\)，计算出所有可能的增加的长度 \(h(i)\)，然后就是求 \(\sum h(i)k(i)\) 在 \([0,w-n]\) 的解的个数，是一个同余最短路。
有一个性质是一个字符串的 \(border\) 长度可以分成 \(\log n\) 个等差数列，因此可以考虑对每个等差数列单独松弛，再考虑合并。
假设有一个首项为 \(a\)，公差为 \(d\)，项数为 \(len\)，同余最短路的模数为 \(a\)，那么这些边连接后会形成 \(\gcd(n,d)\) 个互不影响的环。
考虑对每个环分别松弛，对于某一个环，这个环中 \(dis\) 最小的点一定不会被其它点松弛，于是可以破环为链，考虑一个链上的 \(dp\)。
\[dis(i)\longrightarrow dis(i+kd)(k=1,2\cdots len-1) \]有范围的限制，相当于一个滑动窗口，可以用单调队列优化。
解决了单个等差数列的情况，下面考虑不同等差数列间的合并。
假设上一模数为 \(a_{last}\)，新的模数为 \(a_{now}\)，初始值有 \(dis_{last}(i)\longrightarrow dis_{now}(dis_{last}(i)\bmod{a_{now}})\)。
模 \(a\) 意义下 \(dis(i)\) 的含义是能走到 \(i+ka\)，因此松弛的增量为 \(a_{last}\)，相当于对一个首项为 \(0\)，公差为 \(a_{last}\)，项数为 \(\infty\)，模数为 \(a_{now}\) 的等差数列松弛。
！CF932G Palindrome Partition
很明显，\(n\) 为偶数才存在方案数。
考虑构造一个字符串 \(S=s_1s_ns_2s_{n-1}\cdots\)，这样，就把原问题转化为将 \(S\) 划分成偶回文串的方案数。
考虑 \(dp\)，设 \(f(i)\) 表示前 \(i\) 个字符划分成偶回文的方案数。
转移时需要枚举最后一个串的长度，这相当于是沿回文树上的 \(fail\) 往上跳。
如果直接转移复杂度为 \(O(n^2)\)，考虑优化。
由于结尾的位置是回文串，它的最长回文后缀一定是它的一个 \(border\)，因此也一定满足 \(border\) 能被划分成 \(\log n\) 个等差数列的性质。
于是可以考虑一段等差数列一段等差数列地转移。
由 \(border\) 的性质，对于一段等差数列，只需要考虑等差数列最小的哪项即可（思考），因为其它的贡献会在 \(i-d\) 的位置计算。
！P5287 [HNOI2019]JOJO
没看懂题解，以后再补。
\(\mathbb{LATEX}\)
P4482 [BJWC2018]Border 的四种求法
把问题形式化。
选择一个最大的 \(i\)，满足 \(l\leq i<r\)，且 \(i-l+1\leq lcs(r,i)\)，即 \(i-lcs(r,i)<l\)。
很明显要建出 \(SAM\) 的 \(fail\) 树。
一种比较暴力的方法是，对每个询问，从 \([1,r]\) 对应的节点往上跳，相当于枚举 \(lcs(r,i)=len\)，查询子树中最大的 \(i\) 满足 \(i\in [l,\min(r,l+len))\)，线段树合并解决。
另一种比较暴力的方法是，对每个询问，找到从根当它的路径，将路径上的点和两边的子树内的点加入线段树中，\(i\) 号叶子存 \(val(i)=i-len\)，当走到询问的点时，查询最大的 \(i\)，满足 \(i<r\)，且 \(val(i)<l\)，线段树上二分解决。
综上，使用链分治，然后把询问拆成 \(\log n\) 个，末端的点用第一种方法，重链上较长的连续的点用第二种方法。
P6292 区间本质不同子串个数
求区间颜色数，经典方法为离线后按右端点排序，删除之前的颜色，加入新的颜色。
对于这道题，可以先建出 \(SAM\)，考虑统计每个右端点的答案。
对于 \([1,r]\) 对应的 \(fail\) 树节点，一直往根跳，用线段树维护左端点的答案，并记录当前的右端点（颜色）。
如果暴力跳 \(fail\) 指针时间复杂度不对。
可以 \(LCT\) 维护相同的颜色，又因为每次颜色相同的一定是一条链，所以可以在 \(splay\) 后直接修改。
P4022 [CTSC2012]熟悉的文章
二分答案为 \(mid\)，设 \(dp(i)\) 表示前 \(i\) 个字符所能得到的最大贡献。
\[dp(i)=\max_{j=i-maxlen(i)}^{i-mid}dp(j)+i-j \]预处理出 \(maxlen(i)\)，\(i-maxlen(i)\) 只增不降，使用单调队列维护即可。
标签：11,每个,省选,询问,字符串,fail,节点,等差数列,dis From： https://www.cnblogs.com/yanchengzhi/p/17002011.html