2025.5.28【33OJ NOI 模拟赛 T3】字符串（AC自动机， 字符串后缀结构）

题意

传送门

题意：
给定 $n$ 个字符串 $s_1,s_2\dots ,s_n$，保证它们互不相同。你需要求出满足如下条件的三元组 $(i,j,k)$ 的数量：

• $1\le i,j,j\le n$，且 $i,j,k$ 互不相同。
• $s_i$ 是 $s_j$ 的子串， $s_j$ 是 $s_k$ 的子串。
• 不存在一个 j ′ ∉ { i , j , k } j' \notin \{i, j, k\} j′∈/{i,j,k} 使得 $s_i$ 是 $s_{j^{\prime }}$ 的子串且 $s_{j^{\prime }}$ 是 $s_k$ 的子串。

$1\le n\le 5\times 10^5$，$1\le \sum |s_i|\le 10^6$。保证所有 $s_i$ 仅有小写字母组成。

分析

枚举最长串 $s_k$，那么最短串 $s_i$ 需要是 $s_k$ 的一个子串，我们将 子串 等价成 一个前缀的后缀。
那么枚举 $s_k$ 的一个前缀 $[1,p]$，称前缀 $p$ 的一个 后缀字符串 为能匹配 $[1,p]$ 的后缀的字符串 $s_u$。那么有结论：

• 合法的最短串 $s_i$ 在 $s_k$ 中的任意出现位置上都必须是 最长后缀字符串 或 次长后缀字符串。

正确性显然。因为如果不是最长或次长，那么就至少存在两个 $j$ 满足 $s_i$ 是 $s_j$ 的子串， $s_j$ 是 $s_k$ 的子串。

建出所有 $s_i$ 的 $AC$ 自动机，预处理每个前缀的最长后缀字符串和次长后缀字符串，那么对 $(i,k)$ 的枚举量为 $O(\sum |s_i|)$，$O(n)$ 检验是否存在 有且仅有一个 合法的 $j$，复杂度 $O(n\sum |s_i|)$。

注意到如果一个字符串是某个前缀的后缀字符串，并且它不是最长或次长，那么它一定在 次长字符串对应 $fail$ 树结点的祖先链上，可以通过在 $dfs$ 序上差分，求子树和来判断一个最长或次长后缀字符串是否满足上述 必要条件。

对于所有满足第一个必要条件的字符串 $s_i$，如果 有且仅有一个 $s_j$ 满足 $s_i$ 是 $s_j$ 的子串， $s_j$ 是 $s_k$ 的子串，那么 $(i,k)$ 就可以对答案贡献 $1$。问题是怎么快速判断一个 $s_i$ 是否存在一个合法的 $j$。

只保留满足第一个条件的 $s_i$，那么有结论：

• 对于一个 $s_i$，只需要从 保留的所有字符串中 考虑是否 有且仅有一个 合法的 $j$。

这是因为如果一个字符串 $s_t$ 是 $s_k$ 的子串并且没有被保留下来，那么保留下来的字符串中一定至少有两个包含它。如果一个 $s_i$ 是 $s_t$ 的子串，那么它也一定是那两个包含 $s_t$ 的串的子串，这样就已经不合法了。

但是这样还是不太好直接判断，因为你不可能对每个 $i$ 都枚举保留下来的 $j$。

将 $s_i$ 所有出现的区间取出来，那么可以注意到若 $s_i$ 是某个 $s_j$ 的子串，那么 $s_j$ 的所有出现区间里面都一定会至少包含一个 $s_i$ 对应的区间。
因为 $s_i$ 既然被保留下来了说明任意它出现的位置它都是最长或次长串，那么 $s_i$ 在 $s_j$ 的所有出现位置上都会保留下一个区间。同时也很容易知道如果 $s_i$ 不是 $s_j$ 的子串，那么所有 $s_j$ 的区间里都不可能包含一个 $s_i$ 的区间。

那么我们只需要判断出 包含 $s_i$ 的所有区间中至少一个的区间是否只有一种编号即可。这是简单的 二维偏序 问题。

每次扫描线的区间数量和为 $O(\sum |s_i|)$，总复杂度 $O(\sum |s_i|\times \log (\sum |s_i|))$。

CODE：

#include<bits/stdc++.h>
#define pb emplace_back
#define MP make_pair
using namespace std;
typedef pair< int, int > PII;
const int N = 5e5 + 10;
const int M = 1e6 + 10;
int n, res;
char str[M];
vector< char > s[N];
struct BIT {int c[M];inline int lowbit(int x) {return x & -x;}inline void add(int x, int y) {for(; x < M; x += lowbit(x)) c[x] += y;}inline int ask(int x) {int res = 0; for(; x; x -= lowbit(x)) res += c[x]; return res;}
} T, F;
struct ACAM {int tot, trie[M][26], fail[M], len[M];int et[M], mx[M][2]; // 最长长度， 次长长度不为自身int L[M], R[M], dfc;vector< int > E[M]; // fail 树inline void ins(char *s) {int l = strlen(s + 1);int p = 0;for(int i = 1; i <= l; i ++ ) {if(!trie[p][s[i] - 'a']) trie[p][s[i] - 'a'] = ++ tot, len[trie[p][s[i] - 'a']] = len[p] + 1;p = trie[p][s[i] - 'a'];}et[p] = 1;}void dfs(int x) {L[x] = ++ dfc; for(auto v : E[x]) dfs(v);R[x] = dfc;}inline void build() {queue< int > q;for(int i = 0; i < 26; i ++ ) if(trie[0][i]) q.push(trie[0][i]);while(!q.empty()) {int u = q.front(); q.pop();for(int i = 0; i < 26; i ++ ) {if(trie[u][i]) {fail[trie[u][i]] = trie[fail[u]][i];int x = fail[trie[u][i]], y = trie[u][i];if(et[x]) mx[y][0] = x;if(len[mx[x][0]] > len[mx[y][0]]) swap(mx[y][0], mx[y][1]), mx[y][0] = mx[x][0];else mx[y][1] = (len[mx[y][1]] >= len[mx[x][0]] ? mx[y][1] : mx[x][0]);mx[y][1] = (len[mx[y][1]] >= len[mx[x][1]] ? mx[y][1] : mx[x][1]);q.push(trie[u][i]);}else trie[u][i] = trie[fail[u]][i];}}for(int i = 1; i <= tot; i ++ ) E[fail[i]].pb(i);dfs(0);}
} AC;
struct seg {int l, r, idx;
} P[M * 2];
inline bool cmp(seg x, seg y) {return (x.l < y.l) || (x.l == y.l && x.r > y.r);}
int cov[M], ed[M], nd[M * 2];
inline int calc(int x) { // 计算第 s[x] 作为最长串的答案int p = 0, ct = 0, cn = 0; for(int i = 0; i < s[x].size(); i ++ ) {p = AC.trie[p][s[x][i] - 'a'];int u = (i != s[x].size() - 1 ? (AC.et[p] ? AC.mx[p][0] : AC.mx[p][1]) : AC.mx[p][1]);T.add(AC.L[u], 1);}p = 0; for(int i = 0; i < s[x].size(); i ++ ) {p = AC.trie[p][s[x][i] - 'a'];int a = AC.mx[p][0], b = AC.mx[p][1];if(i != s[x].size() - 1) {if(AC.et[p]) swap(a, b), a = p;}if(a && T.ask(AC.R[a]) - T.ask(AC.L[a]) == 0) P[++ ct] = (seg) {i + 1 - AC.len[a] + 1, i + 1, a}, nd[++ cn] = a;if(b && T.ask(AC.R[b]) - T.ask(AC.L[b]) == 0) P[++ ct] = (seg) {i + 1 - AC.len[b] + 1, i + 1, b}, nd[++ cn] = b;}sort(nd + 1, nd + cn + 1); cn = unique(nd + 1, nd + cn + 1) - (nd + 1);priority_queue< PII > q;sort(P + 1, P + ct + 1, cmp);for(int i = 1; i <= ct; i ++ ) {if(cov[P[i].idx] != -1) {			int c = F.ask(M - 1) - F.ask(P[i].r - 1);if(c > 1) cov[P[i].idx] = -1;else if(c == 1) {if(cov[P[i].idx] != 0) {if(cov[P[i].idx] != q.top().second) cov[P[i].idx] = -1;}else cov[P[i].idx] = q.top().second;}}if(ed[P[i].idx] != 0) F.add(ed[P[i].idx], -1);ed[P[i].idx] = max(ed[P[i].idx], P[i].r); F.add(ed[P[i].idx], 1);q.push(MP(P[i].r, P[i].idx));}int res = 0;for(int i = 1; i <= cn; i ++ ) {res += (cov[nd[i]] > 0); cov[nd[i]] = 0; F.add(ed[nd[i]], -1); ed[nd[i]] = 0;}p = 0;for(int i = 0; i < s[x].size(); i ++ ) {p = AC.trie[p][s[x][i] - 'a'];int u = (i != s[x].size() - 1 ? (AC.et[p] ? AC.mx[p][0] : AC.mx[p][1]) : AC.mx[p][1]);T.add(AC.L[u], -1);}return res;
}
int main() {scanf("%d", &n);for(int i = 1; i <= n; i ++ ) {scanf("%s", str + 1);AC.ins(str); int m = strlen(str + 1);for(int j = 1; j <= m; j ++ ) s[i].pb(str[j]); }AC.build();for(int i = 1; i <= n; i ++ ) res += calc(i);cout << res << endl;return 0;
}