题解区都是 GSAM / SA 做法，唯一几篇 SAM 的题解也讲得不是很清晰。来一发自认为清晰的 SAM 解法。

---

首先写出答案的表达式：

$$\text{ans} = \sum_{l_1,r_1,l_2,r_2} [s_{1[l_1,r_1]}=s_{2[l_2,r_2]}]$$

设 $s_{2[l,r]}$ 在 $s_1$ 中的出现次数为 $\text{cnt}(l,r)$，则上式可以改写成：

$$\text{ans} = \sum_{s_{2[l,r]} \subseteq s_1} \text{cnt}(l,r)$$

考虑直接对串 $s_1$ 建出 SAM，用 $s_2$ 在 SAM 上面跑 LCS（最长公共子串）。没见过 SAM+LCS 的请转 SP1811。

假设目前跑到了 $s_2$ 的第 $m$ 个位置，SAM 上指向的节点为 $p$，匹配长度为 $\text{len}$。那么 $s_{2[1,m]}$ 与 $s_1$ 的最长公共子串的长度就为 $\text{len}$。最长公共子串的每个后缀都是公共子串，所以 $\forall i \in [1,\text{len}]$ 有 $s_{2[m-i+1,m]} \subseteq s_1$，每个 $i$ 对应以 $m$ 结尾的 LCS 的一个后缀。同时 LCS 的每个后缀也是 $s_1$ 的子串，也对应 parent 树上从根到 $p$ 的路径上的一个点。

根据 SAM 的性质，我们把所有 $i$ 按照所对应的 SAM 节点 $p$ 分成若干个连续段，每个连续段中的 $i$ 满足 $\text{cnt}(m-i+1,m)=|\text{endpos}(p)|$。那么第 $m$ 个位置对答案的贡献即为：路径上每个点的 $($ endpos 集合大小 $\times$ 所对应的 $i$ 连续段的长度 $)$。

注意到所有 $p$ 的祖先 $p^\prime$ 都满足 $\text{maxlen}(p^\prime) \le \text{len}$，所以 $p$ 的祖先对应 $i$ 的连续段就是 $[\text{minlen}(p^\prime),\text{maxlen}(p^\prime)]$。而 $p$ 的连续段为 $[\text{minlen}(p),\text{len}]$。我们又知道在 SAM 上 $\text{minlen}(p)=\text{maxlen}(\text{fa}(p))+1$，所以位置 $m$ 对答案的贡献最终表示为

$$\sum_{p^\prime} (\text{maxlen}(p^\prime)-\text{maxlen}(\text{fa}(p^\prime))) \cdot |\text{endpos}(p^\prime)| + (\text{len}-\text{maxlen}(\text{fa}(p))) \cdot |\text{endpos}(p)|$$

endpos 集合大小可以树形 DP 求，$\sum_{p^\prime}$ 一项可以预处理，然后就做完了。

#include <bits/stdc++.h>
using namespace std;

const int N = 2e5 + 5;
typedef long long ll;

int n, m, tot, last;
char s1[N], s2[N];
ll pre[N << 1], siz[N << 1], res = 0;
vector<int> G[N << 1];

struct Node {
    int len, link, ch[26];
    int &operator[](int idx) {
        return ch[idx];
    }
} sam[N << 1];

void build() {
    tot = last = 0;
    sam[0].link = -1, sam[0].len = 0;
}

void extend(int c) {
    int p = last, cur = ++tot;
    sam[cur].len = sam[p].len + 1;
    last = cur;

    while (p != -1 && !sam[p][c]) {
        sam[p][c] = cur;
        p = sam[p].link;
    }

    if (p == -1)
        return sam[cur].link = 0, void();

    int q = sam[p][c];

    if (sam[q].len == sam[p].len + 1)
        return sam[cur].link = q, void();

    sam[++tot].link = sam[q].link;
    sam[tot].len = sam[p].len + 1;

    for (int i = 0; i < 26; ++i)
        sam[tot][i] = sam[q][i];

    sam[q].link = sam[cur].link = tot;

    while (p != -1 && sam[p][c] == q) {
        sam[p][c] = tot;
        p = sam[p].link;
    }
}

void dfs1(int u) {
    for (int v : G[u]) {
        dfs1(v);
        siz[u] += siz[v];
    }
}

void dfs2(int u) {
    int fa = sam[u].link;

    if (u)
        pre[u] += siz[u] * (sam[u].len - sam[fa].len);

    for (int v : G[u]) {
        pre[v] += pre[u];
        dfs2(v);
    }
}

int main() {
    scanf("%s%s", s1 + 1, s2 + 1);
    n = strlen(s1 + 1), m = strlen(s2 + 1);
    build();

    for (int i = 1; i <= n; ++i) {
        extend(s1[i] - 'a');
        siz[last]++;
    }

    for (int i = 1; i <= tot; ++i)
        G[sam[i].link].push_back(i);

    dfs1(0);
    dfs2(0);
    int p = 0, len = 0;

    for (int i = 1; i <= m; ++i) {
        int c = s2[i] - 'a';

        while (p && !sam[p][c]) {
            p = sam[p].link;
            len = sam[p].len;
        }

        if (sam[p][c])
            p = sam[p][c], len++;

        if (!p)
            continue;

        int fa = sam[p].link;
        res += pre[fa] + (len - sam[fa].len) * siz[p];
    }

    printf("%lld\n", res);
    return 0;
}