题意：给定两个字符串，从中各取一个子串使之相同，有多少种取法。允许本质相同。
解：建立广义后缀自动机，对于每个串，分别统计cnt，之后每个点的cnt乘起来。记得开long long
#include <cstdio>
#include <algorithm>
#include <cstring> typedef long long LL;
const int N = ; struct Edge {
int nex, v;
}edge[N << ]; int top; int tr[N][], len[N], fail[N], cnt[N][], vis[N];
int tot = , last, turn, e[N];
char s[N], str[N]; inline void add(int x, int y) {
top++;
edge[top].v = y;
edge[top].nex = e[x];
e[x] = top;
return;
} inline int split(int p, int f) {
int Q = tr[p][f], nQ = ++tot;
len[nQ] = len[p] + ;
fail[nQ] = fail[Q];
fail[Q] = nQ;
memcpy(tr[nQ], tr[Q], sizeof(tr[Q]));
while(tr[p][f] == Q) {
tr[p][f] = nQ;
p = fail[p];
}
return nQ;
} inline int insert(int p, char c) {
int f = c - 'a';
if(tr[p][f]) {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
cnt[Q][turn] = ;
return Q;
}
int t = split(p, f);
cnt[t][turn] = ;
return t;
}
int np = ++tot;
len[np] = len[p] + ;
cnt[np][turn] = ;
while(p && !tr[p][f]) {
tr[p][f] = np;
p = fail[p];
}
if(!p) {
fail[np] = ;
}
else {
int Q = tr[p][f];
if(len[Q] == len[p] + ) {
fail[np] = Q;
}
else {
fail[np] = split(p, f);
}
}
return np;
} void DFS(int x) {
for(int i = e[x]; i; i = edge[i].nex) {
int y = edge[i].v;
DFS(y);
cnt[x][] += cnt[y][];
cnt[x][] += cnt[y][];
}
return;
} int main() {
scanf("%s%s", s, str);
int n = strlen(s), last = ;
for(int i = ; i < n; i++) {
last = insert(last, s[i]);
}
n = strlen(str);
last = turn = ;
for(int i = ; i < n; i++) {
last = insert(last, str[i]);
}
for(int i = ; i <= tot; i++) {
add(fail[i], i);
}
DFS();
int p = ;
LL ans = ;
for(int i = ; i <= tot; i++) {
ans += 1ll * cnt[i][] * cnt[i][] * (len[i] - len[fail[i]]);
} printf("%lld", ans);
return ;
}
AC代码