P4248 [AHOI2013] 差异
求一个定值减去所有后缀的 lcp 的和。
翻转以下序列可以转化成所有前缀的最长后缀，然后建出 SAM 在 parent 树上，对于每一个节点求它是多少对节点的 LCA 即可。
P3181 [HAOI2016] 找相同字符
求两个串的本质不同公共子串数量。
和上题差不多。公共子串等价于两串前缀的公共后缀，那么建广义 SAM 然后子树相乘即可。
#include <bits/stdc++.h>
#define llong long long
#define N 800005
using namespace std;char a[N];
int pos[N], tag[N][3], son[N][32], trsiz = 1;
int fa[N], nxt[N][32], tsiz = 1;
int siz[N][3];
int len[N];
llong ans;inline int insert(int ch, int lst, int in1, int in2){int x = lst, cur = ++tsiz;len[cur] = len[lst]+1;siz[cur][1] += in1, siz[cur][2] += in2;while(x && !nxt[x][ch]) nxt[x][ch] = cur, x = fa[x];if(!x){fa[cur] = 1;return cur;}int y = nxt[x][ch];if(len[y] == len[x]+1){fa[cur] = y;}else{int z = ++tsiz;len[z] = len[x]+1;fa[z] = fa[y];for(int i = 1; i <= 26; ++i)nxt[z][i] = nxt[y][i];while(x && nxt[x][ch] == y)nxt[x][ch] = z, x = fa[x];fa[cur] = fa[y] = z;}return cur;
}vector<int> G[N];
inline void dfs(int u){for(int v : G[u]){dfs(v);siz[u][1] += siz[v][1];siz[u][2] += siz[v][2];}ans += 1ll*(len[u]-len[fa[u]])*siz[u][1]*siz[u][2];return;
}int que[N], he, ta;
int main(){for(int i = 1, l; i <= 2; ++i){scanf("%s", a+1);l = strlen(a+1);int x = 1;for(int j = 1; j <= l; ++j){if(!son[x][a[j]^96]) son[x][a[j]^96] = ++trsiz;x = son[x][a[j]^96];++tag[x][i];}}que[he = ta = 1] = 1;pos[1] = 1;while(he <= ta){int x = que[he++];for(int i = 1; i <= 26; ++i){if(!son[x][i]) continue;pos[son[x][i]] = insert(i, pos[x], tag[son[x][i]][1], tag[son[x][i]][2]);que[++ta] = son[x][i];}}for(int i = 1; i <= tsiz; ++i)G[fa[i]].push_back(i);dfs(1);printf("%lld", ans);return 0;
}