闲话
发现我必须得整个 linux 虚拟机了（
以前因为麻烦没整成功一直在摆着
但是今天这没有 -fsanitize 就寄了
这次一定！
有点晚 就写到这吧
这 cnblogs 不让我发啊 加载不出来
SAM 杂题
统计本质不同子串信息
以【模板】后缀自动机为例。给定一个只包含小写字母的字符串 \(S\)。
你需要求出 \(S\) 的所有出现次数不为 \(1\) 的子串出现次数与该子串长度乘积的最大值。\(1 \le |S| \le 10^6\)。
首先构造出 SAM。
一个子串的出现次数等于其作为一个后缀的前缀出现的次数。由于 SAM 的结构，我们可以设计如下转移求得一个等价类的串的出现次数 \(f(n)\)：
\[f(n) = 1 + \sum_{(n, m)在后缀链接树中} f(m) \]因此可以 \(O(|S|)\) 地求得每个点对应的串出现次数。直接做就行。
写成非递归形式常数会小很多。不写成结构体形式常数会小很多。
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 5e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
struct SAM {
#define len(p) len[p]
#define son(p) son[p]
#define cnt(p) cnt[p]
#define link(p) link[p]
int mlc, lst, lens;
char str[N];
int len[N], link[N], cnt[N], son[N][26];
SAM() { len(0) = 0, link(0) = lens = -1, lst = 0, mlc = 0; }
void clear() { len(0) = 0, link(0) = lens = -1, lst = 0, mlc = 0; }
const char operator[] (const int &p) const { return str[p]; }
char& operator[] (const int &p) { return str[p]; }
char* begin() { return str + 1; }
void extend(int c) {
int now = ++ mlc;
cnt(now) = 1;
len(now) = len(lst) + 1;
int p = lst;
while (~p and !son(p)[c])
son(p)[c] = now, p = link(p);
if (p == -1) link(now) = 0;
else {
int q = son(p)[c];
if (len(p) + 1 == len(q)) link(now) = q;
else {
int kage = ++ mlc;
len(kage) = len(p) + 1, link(kage) = link(q);
memcpy(son(kage), son(q), sizeof(son(kage)));
while (~p and son(p)[c] == q)
son(p)[c] = kage, p = link(p);
link(q) = link(now) = kage;
}
} lst = now;
}
int buk[N], id[N];
void build() {
if (lens == -1) lens = strlen(begin());
rep(i,1,lens) extend(str[i] - 'a');
rep(i,1,mlc) ++ buk[len(i)];
rep(i,1,lens) buk[i] += buk[i - 1];
rep(i,1,mlc) id[buk[len(i)] -- ] = i;
pre(i,mlc,1) cnt(link(id[i])) += cnt(id[i]);
}
int calc() {
int ans = 0;
rep(i,1,mlc) if (cnt(i) > 1)
ans = max(ans, cnt(i) * len(i));
return ans;
}
} S;
signed main() {
cin >> S.begin();
S.build();
cout << S.calc();
}
第 \(k\) 小子串问题
以 [TJOI2015]弦论 为例。对于一个给定的长度为 \(n\) 的字符串，求出它的第 \(k\) 小子串。\(t\) 为 \(0\) 则表示不同位置的相同子串算作一个，\(t\) 为 \(1\) 则表示不同位置的相同子串算作多个。
\(1\le n \le 5\times 10^5, t\in \{0, 1\}, 1\le n \le 10^9\)。
首先需要处理出每个节点对应会贡献几个子串。当 \(t = 1\) 时按前一题的方式处理，\(t = 0\) 则 \(\forall f(n) = 1\)。
随后按照搜索树的形式寻找即可。由于边表示的是串末尾加入字符的转移，我们只需要作子树贡献和。如果当前 \(k\) 大于子树和就跳过子树，\(k\) 减去子树和；反之答案在这棵子树内，我们只需要递归入这棵子树即可。
容易在 \(O(n|\Sigma|)\) 的复杂度内得到答案。
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 5e6 + 10;
const int inf = 0x3f3f3f3f;
const ll infll = 0x3f3f3f3f3f3f3f3fll;
int t, k;
struct SAM {
#define len(p) len[p]
#define son(p) son[p]
#define sum(p) sum[p]
#define cnt(p) cnt[p]
#define link(p) link[p]
int mlc, lst, lens;
char str[N];
int len[N], link[N], cnt[N], sum[N], son[N][26];
SAM() { lst = 1, mlc = 1; }
void clear() { lst = 1, mlc = 1; }
const char operator[] (const int &p) const { return str[p]; }
char& operator[] (const int &p) { return str[p]; }
char* begin() { return str + 1; }
void extend(int c) {
int now = ++ mlc;
cnt(now) = 1;
len(now) = len(lst) + 1;
int p = lst;
while (p and !son(p)[c])
son(p)[c] = now, p = link(p);
if (p == 0) link(now) = 1;
else {
int q = son(p)[c];
if (len(p) + 1 == len(q)) link(now) = q;
else {
int kage = ++ mlc;
len(kage) = len(p) + 1, link(kage) = link(q);
memcpy(son(kage), son(q), sizeof(son(kage)));
while (p and son(p)[c] == q)
son(p)[c] = kage, p = link(p);
link(q) = link(now) = kage;
}
} lst = now;
}
int buk[N], id[N];
void build() {
if (lens <= 0) lens = strlen(begin());
rep(i,1,lens) extend(str[i] - 'a');
rep(i,1,mlc) ++ buk[len(i)];
rep(i,1,lens) buk[i] += buk[i - 1];
rep(i,1,mlc) id[buk[len(i)] -- ] = i;
pre(i,mlc,1) {
if (t) cnt(link(id[i])) += cnt(id[i]);
else cnt(id[i]) = 1;
} cnt(1) = 0;
pre(i,mlc,1) {
sum(id[i]) = cnt(id[i]);
rep(j,0,25) if (son(id[i])[j])
sum(id[i]) += sum(son(id[i])[j]);
}
}
void calc() {
if (k > sum(1)) { puts("-1"); return; }
int ptr = 1;
k -= cnt(1);
while (k > 0) {
int now = 0;
while (k > sum(son(ptr)[now])) {
k -= sum(son(ptr)[now]);
++ now;
} ptr = son(ptr)[now];
putchar(now + 'a');
k -= cnt(ptr);
}
}
} S;
signed main() {
ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
cin >> S.begin() >> t >> k;
S.build();
S.calc();
}
提取后缀链接树 - \(LCP = \text{len}(LCA)\)
以 SvT 为例。有一个长度为 \(n\) 的仅包含小写字母的字符串 \(S\)，下标范围为 \([1,n]\)。
现在有若干组询问，对于每一个询问，我们给出 \(t\) 个后缀（以其在 \(S\) 中出现的起始位置来表示），求这些后缀两两之间的 \(LCP\) 的长度之和。一对后缀之间的 \(LCP\) 长度仅统计一遍。
\(n\le 5\times 10^5, \ \sum t\le 3\times 10^6\)。
我们首先考虑如何刻画 \(LCP\)。
我们建出 \(S\) 的反串的 \(SAM\)，提取后缀链接树。由引理可以得到这棵树对应了原串的后缀树。由经典结论有两个子串的 \(LCP\) 长度就是它们在后缀树上 \(LCA\) 位置的 \(\text{len}\)。
因此我们就将问题转换到了树上。重新叙述问题：
给定一棵树和一些节点，我们需要统计这些节点两两的 \(LCA\) 的权值和。节点数总和不超过 \(O(n\log n)\) 对应的 \(n\)。
一眼虚树。我们首先建出节点对应的虚树，随后在其上 dfs。一个节点对答案的贡献是其不同子树节点数之积的和乘上这个节点的权值。
直接做就行。
朴素做法是 \(O(n\log n + \sum t)\) 的。大概有其他神奇做法。
码量很大？不是很懂。
换了从 yhw 那第一次见到的无主函数外函数的写法（
code
#include <bits/stdc++.h>
using namespace std;
#define rep(i,s,t) for (register int i = (s), i##_ = (t) + 1; i < i##_; ++ i)
#define pre(i,s,t) for (register int i = (s), i##_ = (t) - 1; i > i##_; -- i)
const int N = 1e6 + 10;
int n, m;
char ch[N];
signed main() {
ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
cin >> n >> m >> ch + 1;
reverse(ch + 1, ch + 1 + n);
static int mlc = 1, lst = 1, link[N], len[N], son[N][26];
auto extend = [](int c) {
int now = ++ mlc, p = lst;
len[now] = len[p] + 1;
while (p and !son[p][c])
son[p][c] = now, p = link[p];
if (!p) link[now] = 1;
else {
int q = son[p][c];
if (len[q] == len[p] + 1) link[now] = q;
else {
int kage = ++ mlc;
len[kage] = len[p] + 1, link[kage] = link[q];
link[q] = link[now] = kage;
memcpy(son[kage], son[q], sizeof son[kage]);
while (p and son[p][c] == q)
son[p][c] = kage, p = link[p];
}
} lst = now;
};
static int pos[N], ivi[N];
rep(i,1,n) extend(ch[i] - 'a'), pos[lst] = n - i + 1, ivi[n - i + 1] = lst;
static vector<int> g[N];
rep(i,2,mlc) g[link[i]].emplace_back(i);
static int dfn[N], dep[N], stp = 0, fa[N], st[N][21], lgv[N];
function<void(int, int)> dfs;
dfs = [&](int u, int fat) {
dfn[u] = ++ stp, fa[u] = fat;
dep[u] = dep[fat] + 1;
for (auto v : g[u]) dfs(v, u);
};
dfs(1, 0);
rep(i,1,mlc) st[dfn[i]][0] = fa[i];
rep(i,2,mlc) lgv[i] = lgv[i >> 1] + 1;
rep(i,1,lgv[mlc]) for (int j = 1, u, v; j + (1 << i) - 1 <= mlc; ++ j)
u = st[j][i - 1], v = st[j + (1 << i - 1)][i - 1], st[j][i] = dep[u] < dep[v] ? u : v;
function<int(int, int)> lca = [](int u, int v) {
if (u == v) return u;
u = dfn[u], v = dfn[v];
if (u > v) swap(u, v); ++ u;
int d = lgv[v - u + 1];
u = st[u][d], v = st[v - (1 << d) + 1][d];
return dep[u] < dep[v] ? u : v;
};
static vector<int> e[N];
auto adde = [](int u, int v) { e[u].emplace_back(v); };
static int stk[N], top, ck[N], top2;
static int t, tmp, nde[N], cnt[N];
while (m --) {
cin >> t;
rep(i,1,t) cin >> tmp, nde[i] = ivi[tmp], cnt[nde[i]] = 1;
sort(nde + 1, nde + 1 + t, [](int a, int b){ return dfn[a] < dfn[b]; });
t = unique(nde + 1, nde + 1 + t) - nde - 1;
stk[top = 1] = 1; ck[top2 = 1] = 1;
rep(i,1,t) {
if (nde[i] == 1) continue;
int LCA = lca(nde[i], stk[top]);
while (dep[LCA] < dep[stk[top-1]]) {
adde(stk[top-1], stk[top]);
top--;
} if (LCA != stk[top]) {
adde(LCA, stk[top]);
if (LCA != stk[top-1]) stk[top] = LCA, ck[++ top2] = LCA;
else top--;
} stk[++top] = nde[i], ck[++ top2] = nde[i];
} while (-- top) adde(stk[top], stk[top + 1]);
long long ans = 0;
static bool vis[N];
function <void(int, int)> dfs2;
dfs2 = [&](int u, int fat) {
vis[u] = 1;
for (auto v : e[u]) if (v != fat) {
dfs2(v, u);
ans += 1ll * len[u] * cnt[u] * cnt[v];
cnt[u] += cnt[v];
}
};
dfs2(1, 0);
cout << ans << endl;
rep(i,1,top2) e[ck[i]].clear(), e[ck[i]].shrink_to_fit(), cnt[ck[i]] = 0;
}
}
调这题给我调吐了。最后发现是 st 表数组开小了。寄。
标签：mlc,20,int,闲话,len,son,22.12,link,now From： https://www.cnblogs.com/joke3579/p/chitchat221220.html