P4248 [AHOI2013] 差异
这个 \(SAM\) 版的其实很简单。
因为要求 \(lcp\)，所以先把字符串翻转，这样翻转过后的字符串的后缀就是原来字符串的前缀了。
然后题目要我们求最长长度，并且我们已经转化成后缀了，那么就在 \(parent\) 树上考虑。
显然，对于我们 \(parent\) 树上某个节点 \(x\) 的儿子们 \(i, j, k\)，在 \(i, j, k\) 节点上的后缀不相等，当且仅当 \(i, j, k\) 节点上的后缀去掉前面一部分后才能相当，也就是去掉前面的部分直到长度成为节点 \(x\) 的 \(length\) 的时候是最长且相等。
那么这个时候我们统计 \(i, j, k\) 之间能配对的数量再乘上 \(length[x] * 2\) （内个 \(2\) 是题目要乘的）就是我们要减去的答案。
元旦
#include <bits/stdc++.h>
const int MAXN = 3 * (5e5 + 1000);
long long answer;
class Suffix_Automaton {
private:
int root, tot, last;
int child[MAXN][27];
int link[MAXN], length[MAXN], count[MAXN];
public:
Suffix_Automaton() {
root = tot = last = 1;
}
void Insert(int c) {
int p = last, newP = ++ tot;
last = newP;
length[newP] = length[p] + 1;
count[newP] = 1;
while (p && !child[p][c]) {
child[p][c] = newP;
p = link[p];
}
if (!p) {
link[newP] = root;
}
else {
int q = child[p][c];
if (length[q] == length[p] + 1) {
link[newP] = q;
}
else {
int newQ = ++ tot;
memcpy(child[newQ], child[q], sizeof child[q]);
length[newQ] = length[p] + 1;
link[newQ] = link[q];
link[q] = link[newP] = newQ;
while (p && child[p][c] == q) {
child[p][c] = newQ;
p = link[p];
}
}
}
}
std::vector<int> son[MAXN];
void Build() {
for (int i = 1; i <= tot; ++ i)
son[link[i]].emplace_back(i);
}
void Dfs(int now) {
for (const int &iter: son[now]) {
Dfs(iter);
answer -= 2ll * count[now] * count[iter] * length[now];
count[now] += count[iter];
}
}
}sam;
int N;
char ch[MAXN];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> (ch + 1);
N = strlen(ch + 1);
std::reverse(ch + 1, ch + 1 + N);
for (int i = 1; i <= N; ++ i) {
answer += 1ll * i * (N - 1);
sam.Insert(ch[i] - 'a' + 1);
}
sam.Build();
sam.Dfs(1);
std::cout << answer << '\n';
return 0;
}
P2178 [NOI2015] 品酒大会
这个其实和上面的差异同理，基本上上面的差异会了，这个品酒大会就会了（仅限于 \(SAM\)，\(SA\) 的做法可以说是毫不相干？？？）。
这里面相当于要找 \(lcp(i,j)>=r\) 的数量，并且要求 \(max\{P_i \cdot P_j\}\)。
我们在差异里面求的是 \(length[x]\) 的数量，那么这个我们就直接后缀和就好了。
那么最大值呐？？？
还是跟数量的求法一样，对于 \(length[x]\) 维护最大次大最小次小（有负数）的值就行了，每次对于每个节点的取个 \(max\) 就好了。
我们可以发现对于每个不相交的子树之间是不存在 \(right(endpos)\) 集合存在相交的情况，所以就可以不重不漏了。
（顺便说一句：这题用 \(SAM\) 是真香，比 \(SA\) 好写多了）。
春节
#include <bits/stdc++.h>
const int MAXN = 3 * (3e5 + 1000);
int N;
char ch[MAXN / 3];
int value[MAXN / 3];
std::pair<long long, long long> answer[MAXN / 3];
class Suffix_Automaton {
private:
int root, tot, last;
int child[MAXN][27];
int link[MAXN], length[MAXN], count[MAXN];
std::pair<int, int> max[MAXN], min[MAXN];
std::pair<int, int> Max(const std::pair<int, int> &a, const std::pair<int, int> &b) {
std::pair<int, int> result;
if (a.first > b.first) {
result.first = a.first;
if (a.second > b.first)
result.second = a.second;
else
result.second = b.first;
}
else {
result.first = b.first;
if (b.second > a.first)
result.second = b.second;
else
result.second = a.first;
}
return result;
}
std::pair<int, int> Min(const std::pair<int, int> &a, const std::pair<int, int> &b) {
std::pair<int, int> result;
if (a.first < b.first) {
result.first = a.first;
if (a.second < b.first)
result.second = a.second;
else
result.second = b.first;
}
else {
result.first = b.first;
if (b.second < a.first)
result.second = b.second;
else
result.second = a.first;
}
return result;
}
public:
Suffix_Automaton() {
root = tot = last = 1;
}
void Insert(int c, int pos) {
int p = last, newP = ++ tot;
max[newP].first = min[newP].first = value[pos];
max[newP].second = -1e9 - 1;
min[newP].second = 1e9 + 1;
count[newP] = 1;
last = newP;
length[newP] = length[p] + 1;
while (p && !child[p][c]) {
child[p][c] = newP;
p = link[p];
}
if (!p) {
link[newP] = root;
}
else {
int q = child[p][c];
if (length[q] == length[p] + 1) {
link[newP] = q;
}
else {
int newQ = ++ tot;
max[newQ].first = max[newQ].second = -1e9 - 1;
min[newQ].first = min[newQ].second = 1e9 + 1;
memcpy(child[newQ], child[q], sizeof child[q]);
length[newQ] = length[p] + 1;
link[newQ] = link[q];
link[q] = link[newP] = newQ;
while (p && child[p][c] == q) {
child[p][c] = newQ;
p = link[p];
}
}
}
}
std::vector<int> son[MAXN];
void Build() {
for (int i = 1; i <= tot; ++ i)
son[link[i]].emplace_back(i);
}
void Dfs(int now) {
if (!son[now].size())
return;
for (const int &iter: son[now]) {
Dfs(iter);
answer[length[now]].first += 1ll * count[now] * count[iter];
max[now] = Max(max[now], max[iter]);
min[now] = Min(min[now], min[iter]);
count[now] += count[iter];
}
long long result = std::max(1ll * max[now].first * max[now].second, 1ll * min[now].first * min[now].second);
answer[length[now]].second = std::max(answer[length[now]].second, result);
}
}sam;
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N >> (ch + 1);
for (int i = 1; i <= N; ++ i) {
answer[i - 1].second = -1e18 - 1;
std::cin >> value[i];
}
std::reverse(ch + 1, ch + 1 + N);
std::reverse(value + 1, value + 1 + N);
for (int i = 1; i <= N; ++ i) {
sam.Insert(ch[i] - 'a' + 1, i);
}
sam.Build();
sam.Dfs(1);
for (int i = N - 2; i >= 0; -- i) {
answer[i].first += answer[i + 1].first;
answer[i].second = std::max(answer[i].second, answer[i + 1].second);
}
for (int i = 0; i <= N - 1; ++ i) {
std::cout << answer[i].first << ' ';
if (answer[i].second == -1e18 - 1)
std::cout << 0 << '\n';
else
std::cout << answer[i].second << '\n';
}
return 0;
}
P6139 【模板】广义后缀自动机（广义 SAM）
就是多个串放到一个 \(SAM\) 里面，还是挺简单的，比刚学 \(SAM\) 好多了。
元宵节
#include <bits/stdc++.h>
const int MAXN = 3e6 + 1000;
class Trie {
private:
int tot, root;
public:
int last[MAXN / 3];
int child[MAXN / 3][26];
int number[MAXN / 3];
Trie() {
root = tot = 1;
last[root] = 1;
}
void BuildTree(char *str) {
int n = strlen(str + 1);
int now = root, ch;
for (int i = 1; i <= n; ++ i) {
ch = str[i] - 'a';
if (child[now][ch] == 0) {
child[now][ch] = ++ tot;
number[tot] = ch;
}
now = child[now][ch];
}
}
}trie;
class Suffix_Automaton {
private:
int link[MAXN], length[MAXN];
public:
int root, tot;
int child[MAXN][26];
Suffix_Automaton() {
root = tot = 1;
}
int Insert(int c, int last) {
int p = last, newP = ++ tot;
length[newP] = length[p] + 1;
while (p && !child[p][c]) {
child[p][c] = newP;
p = link[p];
}
if (!p) {
link[newP] = root;
}
else {
int q = child[p][c];
if (length[q] == length[p] + 1) {
link[newP] = q;
}
else {
int newQ = ++ tot;
memcpy(child[newQ], child[q], sizeof child[q]);
length[newQ] = length[p] + 1;
link[newQ] = link[q];
link[q] = link[newP] = newQ;
while (p && child[p][c] == q) {
child[p][c] = newQ;
p = link[p];
}
}
}
return newP;
}
}sam;
inline void Bfs() {
std::queue<std::pair<int, int>> queue;
for (int i = 0; i <= 25; ++ i)
if (trie.child[1][i])
queue.emplace(1, trie.child[1][i]);
while (!queue.empty()) {
int father = queue.front().first;
int now = queue.front().second;
queue.pop();
trie.last[now] = sam.Insert(trie.number[now], trie.last[father]);
for (int i = 0; i <= 25; ++ i)
if (trie.child[now][i])
queue.emplace(now, trie.child[now][i]);
}
}
bool visit[MAXN];
long long count[MAXN];
inline void Dfs(int now) {
if (visit[now] || now == 0)
return;
visit[now] = true;
if (now != 1)
count[now] = 1;
for (int i = 0; i <= 25; ++ i) {
int to = sam.child[now][i];
Dfs(to);
count[now] += count[to];
}
}
int N;
char ch[MAXN];
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N;
for (int i = 1; i <= N; ++ i) {
std::cin >> (ch + 1);
trie.BuildTree(ch);
}
Bfs();
Dfs(1);
std::cout << count[1] << '\n' << sam.tot << '\n';
return 0;
}
P3346 [ZJOI2015] 诸神眷顾的幻想乡
仔细读题发现叶子结点只有 \(20\) 个，那么以每个叶子结点为根，把根到其他叶子结点路径上的字符串加入 \(Trie\) 中就行。
妇女节
#include <bits/stdc++.h>
const int MAXN = 4e6 + 1000;
int N, C;
int color[110000], degree[110000];
int cnt = 1, head[210000], next[210000], to[210000];
void AddEdge(int u, int v) {
++ cnt;
next[cnt] = head[u];
head[u] = cnt;
to[cnt] = v;
}
class Trie {
private:
int root, tot;
public:
int child[MAXN][11], number[MAXN], last[MAXN];
Trie() {
root = tot = 1;
last[1] = 1;
}
void BuildTrie(int *array, int n) {
int now = root;
for (int i = 1; i <= n; ++ i) {
int c = array[i];
if (!child[now][c]) {
child[now][c] = ++ tot;
number[tot] = c;
}
now = child[now][c];
}
}
}trie;
class Suffix_Automaton {
private:
int root, tot;
public:
int child[MAXN][11], link[MAXN], length[MAXN];
Suffix_Automaton() {
root = tot = 1;
}
int Insert(int c, int last) {
int p = last, newP = ++ tot;
length[newP] = length[p] + 1;
while (p && !child[p][c]) {
child[p][c] = newP;
p = link[p];
}
if (!p) {
link[newP] = root;
}
else {
int q = child[p][c];
if (length[q] == length[p] + 1) {
link[newP] = q;
}
else {
int newQ = ++ tot;
memcpy(child[newQ], child[q], sizeof child[q]);
length[newQ] = length[p] + 1;
link[newQ] = link[q];
link[q] = link[newP] = newQ;
while (p && child[p][c] == q) {
child[p][c] = newQ;
p = link[p];
}
}
}
return newP;
}
}sam;
bool visit[110000];
int tempSum, str[110000];
void GetString(int now) {
visit[now] = true;
str[++ tempSum] = color[now];
int nowLen = tempSum;
if (degree[now] == 1) {
trie.BuildTrie(str, nowLen);
}
for (int i = head[now]; i; i = next[i]) {
if (visit[to[i]])
continue;
tempSum = nowLen;
GetString(to[i]);
}
}
void Bfs() {
std::queue<std::pair<int, int>> queue;
for (int i = 0; i <= C - 1; ++ i)
if (trie.child[1][i])
queue.emplace(1, trie.child[1][i]);
while (queue.size()) {
int father = queue.front().first;
int now = queue.front().second;
queue.pop();
trie.last[now] = sam.Insert(trie.number[now], trie.last[father]);
for (int i = 0; i <= C - 1; ++ i)
if (trie.child[now][i])
queue.emplace(now, trie.child[now][i]);
}
}
bool flag[MAXN];
long long count[MAXN];
void Dfs(int now) {
if (flag[now] || now == 0)
return;
flag[now] = true;
if (now != 1)
count[now] = 1;
for (int i = 0; i <= C - 1; ++ i) {
Dfs(sam.child[now][i]);
count[now] += count[sam.child[now][i]];
}
}
int main() {
std::ios::sync_with_stdio(false);
std::cin.tie(0);
std::cout.tie(0);
std::cin >> N >> C;
for (int i = 1; i <= N; ++ i)
std::cin >> color[i];
for (int i = 1, u, v; i <= N - 1; ++ i) {
std::cin >> u >> v;
AddEdge(u, v);
AddEdge(v, u);
degree[u] ++;
degree[v] ++;
}
for (int i = 1; i <= N; ++ i) {
if (degree[i] > 1)
continue;
memset(visit, 0, sizeof(visit));
tempSum = 0;
GetString(i);
}
Bfs();
Dfs(1);
std::cout << count[1] << '\n';
return 0;
}