int ans;
inline void sol() {
int p = 1, mxlen = 0;
for (register int i = 1; i <= n; ++i) {
int c = s[i] - 'a';
while (p && !son[p][c]) p = fa[p], mxlen = len[p];
if (!p) {
mxlen = 0, p = 1;
continue;
}
p = son[p][c]; mxlen++;
ans = max(ans, mxlen);
}
}
两串的公共子串个数
例题 : P4770 [NOI2018]你的名字
题意：给出一个长串 S ，然后给出一堆短串 T，给 T 同时给出 L, R，询问有多少串 不属于S 的子串，但属于 T的子串。
可以转化成求两串的公共子串个数。
shadowice大佬的题解
转化成对于 T 的每个前缀，求有多少串是 S 的子串。然而还不对，最后还要去重。
去重可以在 T 的后缀自动机上进行。
具体来说，对于 T 的 SAM 上的每一个节点，记录一下其管辖的子串（指的是从根能到达的子串)中有多少子串属于 S 的子串。
发现对于每个节点 cur，其管辖范围的子串是连续的（前面已经提到过）；如果其中某个长串属于 S，那么其子串一定是 S 的子串。因此我们转而求 每个节点中最长的 属于 S 的子串的串长度。 我们记此为 mx[]。
求每个前缀在 S 中的最长子串？已经就有点 求最长公共子串 的意思了。
还是那样，每拓展一个字符，S 的 DFA 上最多往下跑一个节点；如果一个可以跑的节点都没有，就尝试往 fa 上跳（类似AC自动机），再进行尝试。往 fa 上跳，就说明我们的子串变小了，那么 T 上自动机的点可能（肯定）就不合法了（比如 abbaa 变成了 baa）。怎么办呢？
幸运的是，我们发现，因为我们跳 fa 只会砍掉开头的几个字母，串的 endpos 还是那几个，可能还会多一些。那么我们就在 T 的自动机上跳 fa。最后找到合法的 S 位置和合法的 T 位置后，用 nwlen（当前串长度）来更新 mx[] 即可。
和下面（求多串的最长公共子串）同理，如果 T 上某一个节点能匹配 nwlen,其祖先也可以匹配 nwlen，但是不能超过其 len。
```cpp
int np_s = 1, np_t = 1, nwlen = 0;
int ct = 0;
for (register int i = 1; i <= t_n; ++i) {
int c = s[i] - 'a';
while (np_s && !S.son[np_s][c]) np_s = S.fa[np_s]
nwlen++;
np_s = S.son[np_s][c]; np_t = T.son[np_t][c];
while (T.len[T.fa[np_t]] + 1 > nwlen) np_t = T.fa[np_t];
int p = np_t;
while (T.mx[p] != T.len[p] && p)
T.mx[p] = max(T.mx[p], min(nwlen, T.len[p])), p = T.fa[p];
}
for (register int i = 2; i <= T.tot; ++i) {
res -= max(T.mx[i] - T.len[T.fa[i]], 0ll);
}
```
### 求多串的最长公共子串
[SP1812 LCS2 - Longest Common Substring II](https://www.luogu.com.cn/problem/SP1812)
[SP10570 LONGCS - Longest Common Substring](https://www.luogu.com.cn/problem/SP10570)
对其中一个串做 SAM，然后还是上回的思路，只不过这我们要记录每个节点的匹配的最大值，然后众串取个最小，最后每个节点取个最大。
~~众所周知~~，每个节点代表一些长度连续的区间，我们的任务是找出每个其他串能匹配的最长长度，这样，能匹配长度为 4 的子串就一定能匹配长度为 3 的子串，但能匹配长度为 3 的子串不一定能匹配长度为 4 的子串.因此我们需要各串的答案中取个最小值，这个最小值所代表的串一定在所有串中出现。
最终把所有这样能在所有串中出现的局部最大值（对于每个节点而言）再取个 $max$ 就是全局最大值（对于所有串而言）。
然而会被 $hack$ 掉。
```
abcba
ab
ba
```
答案显然是1（"a"或"b")，但看看我们做的好事：
我们只经过了 $5,6,2,3$ 节点，并且每个都只经过了一次，答案当然为 0.
哪里有问题？发现 6 节点答案一定可以作为 2 节点答案，因为 2 节点的串全是 6 节点的串的子串，6节点的 $abba,bba,ba$ 中能搞到长度为 2 的最长公共子串，那么 2 节点的 $a$ 就也应该能搞到长度为 2 的子串（如果有的话）；又因为 2 节点最长才为 1，所以需要和 1 取一个 $min$。
是不是有点像 AC 自动机的部分操作？
总结一下：
首先对一个串建立 SAM
然后把其他串拿过来再 SAM 的 DFA 上跑，并记录每个节点能搞到的最长长度。
接着我们把每个节点的最长长度传递给 $fa$（当然是按照 $len$ 递减的顺序），并且更新当前节点的公共长度（取 $min$）。
最后我们找出所有节点公共长度的最大值，作为答案。
$Code:
//for every other string
int p = 1, res = 0;
for (register int i = 1; i <= n; ++i) {
int c = s[i] - 'a';
while (p && !son[p][c]) p = fa[p], res = len[p];
if (!p) {
res = 0, p = 1;
continue;
}
res++; p = son[p][c];
nwmx[p] = max(nwmx[p], res);
}
for (register int i = tot; i; --i) {
int p = id[i];
nwmx[fa[p]] = max(nwmx[fa[p]], min(len[fa[p]], nwmx[p]));
mn[p] = min(mn[p], nwmx[p]);
nwmx[p] = 0;
}
//at last
for (register int i = 1; i <= tot; ++i) {//only one string
ans = max(ans, mn[i]);
}
求多串的公共子串数量
并没有找到相关题目和题解，只有一个这个
我的大致思路是 结合前三种问题。第二种问题我们拿到 T 上搞，主要是因为 S 太长了，一个就 5e5；并且询问太多了，一共有 1e5 次询问，并且每次询问还有不同的 L, R，不好离线。