这个专题只是用来记录刷题的，不放代码了，而且以前刷过不少的都不会放上来。只记录从2019.10.31后的。

[Poi2000]公共串

给出几个串，问你他们的最长公共子串。

SOLUTION：其实这题因为长度太小，所以SAM和广义SAM都随便做。 SAM的话，取最小的串建SAM，然后用其他的串在上面跑，每次更新每个节点匹配的最长len，每次再对答案取min就行，这样的复杂度就是$O(minlen\ast n)$的。 如果是广义SAM，建好了之后树上打标记，拓扑排序就可以维护啦。 但是这样的复杂度是$O(maxlen\ast n)$的。

2019南京区域赛热身赛D

题意就是，给你若干个串，命名为$T_1,T_2,...,T_n$，需要计算 $$\sum _{\forall stringS}\prod _{i=1}^n{r}_i(S)$$ 其中$r_i(S)$表示$S$这个串在$T_i$中作为子串出现了多少次。 数据范围满足${\sum }_{i=1}^{n}strlen(T_i)\le 8e5$。

SOLUTION：用SAM的话同上，取最小的串建SAM，然后每次跑一遍维护一下每个节点的right即可。 如果是广义SAM，就很日了。因为$O(maxlen\ast n)$是不可以接受的，所以你需要虚树，每次打标记的时候，在虚树上差分，打乘法标记，以及要对一些节点清0，于是还需要打被多少个串覆盖了的标记。

BZOJ 4180 字符串计数

题意：给你一个字符串T，你可以选择它的若干子串拼成长为n的字符串S，定义S的拼接次数为最少的子串个数使得他们拼起来为S，现在给出T和n，问你对于所有的S来说，最大的拼接次数为多少？ SOLUTION：因为子串的特殊性质，所以只要判断这个子串往后拼接的下一个子串的首字符是否能和这个子串拼起来得到的还是T中的子串就行（因为你要加入的子串长度应该是极大的），那么你考虑对于全局来说，也就是可以用$f_{i,j}$来表示$i$这个字母后面拼$j$这个字母在满足极大情况下的最短长度是多少。 接下来就是考虑怎么求$f_{i.j}$，建SAM，极大这个条件会表现为$st$这个状态是否有$j$这个儿子。（在转移的trie中考虑），那么设$g_{i,j}$表示$i$这个状态后面不能接$j$这个字母的最小长度。 转移就是 $$g_{i,j}=min(g_{ch[i][k],j}),ifch[i][k]!=NULL$$ 初值为$g_{i,j}=1,ifch[i][j]==NULL$ 和 $g_{i,j}=INF,ifch[i][j]!=NULL$ 然后我们可以二分答案，然后MIN-PLUS Product来获得这样的长度是否会小于等于n Remark：貌似数据有点问题，比如 $4$ $DDAABBDDBD$ 这个答案是3不是4，但是所有A掉的代码都是4…好像是他们认为如果最后二分完的答案不够N的长度的话要+1？然而因为定义的是最小操作次数所以不应该+1（x