题目大意：给你两个字符串，求从两个字符串中各选择一个字串使得这两个字串相同的方案数。
题解：建广义$SAM$，对每个点求出在第一个串中出现次数和第二个串中出现次数，乘起来就行了
卡点：无
C++ Code：
#include#include #include #define maxn 200010namespace SAM {#define N (maxn << 2) int R[N], nxt[N][26], fail[N]; int lst = 1, idx = 1, sz[N][2]; void append(char __ch, int op) { int ch = __ch - 'a'; int p = lst, np = lst = ++idx; R[np] = R[p] + 1; sz[np][op] = 1; for (; p && !nxt[p][ch]; p = fail[p]) nxt[p][ch] = np; if (!p) fail[np] = 1; else { int q = nxt[p][ch]; if (R[q] + 1 == R[p]) fail[np] = q; else { int nq = ++idx; fail[nq] = fail[q], R[nq] = R[p] + 1, fail[q] = fail[np] = nq; std::copy(nxt[q], nxt[q] + 26, nxt[nq]); for (; p && nxt[p][ch] == q; p = fail[p]) nxt[p][ch] = nq; } } } int head[N], cnt; struct Edge { int to, nxt; } e[N]; inline void addedge(int a, int b) { e[++cnt] = (Edge) {b, head[a]}; head[a] = cnt; } long long ans; void dfs(int u) { for (int i = head[u]; i; i = e[i].nxt) { int v = e[i].to; dfs(v); sz[u][0] += sz[v][0], sz[u][1] += sz[v][1]; ans += static_cast (R[v] - R[u]) * sz[v][0] * sz[v][1]; } } long long work() { for (int i = 2; i <= idx; i++) addedge(fail[i], i); dfs(1); return ans; }#undef N}int n;char s[maxn];int main() { scanf("%s", s); n = strlen(s); for (int i = 0; i < n; i++) SAM::append(s[i], 0); scanf("%s", s); n = strlen(s); SAM::lst = 1; for (int i = 0; i < n; i++) SAM::append(s[i], 1); printf("%lld\n", SAM::work()); return 0;}